作　　者： ; ; ;

机构地区： 中山大学人文科学学院逻辑与认知研究所

出　　处： 《逻辑学研究》 2016年第2期14-31,共18页

摘　　要： 直观地说,简洁性是指一个逻辑系统紧凑表示问题的能力。近年来关于简洁性的研究逐渐得到人们的关注。本文将讨论两类逻辑程序,即基数约束程序(Cardinality Constraint Programs,CCP)与前提嵌套程序(Nested Logic Programs,NLP)之间的简洁性。我们设计了一个从CCP到NLP多项式长度的等价翻译,这极大改进了Ferraris和Lifschitz提出的指数长度翻译方法,由此证明NLP至少与CCP一样简洁。 Simply speaking, succinctness means the ability of a logical system to compactly represent a problem. Recently, the study of succinctness has gained a lot of attention. In this paper, we will discuss the succinctness between two classes of logic programs, that is, cardinality constraint programs(CCP) and nested logic programs(NLP). We prove that NLP is at least as succinct as CCP, it means every CCP program can be equivalently translated into a NLP program within polynomial-size growth. This significantly improves the result of Ferraris and Lifschitz, which states that every CCP program can be equivalently translated into an exponential-size NLP program.

关 键 词： 简洁性 回答集 基数约束程序 前提嵌套程序

领　　域： [哲学宗教]