前提嵌套程序和基数约束程序的简洁性研究

On the Succinctness of Logic Programs with Nested Bodies and Cardinality Constraints

直观地说,简洁性是指一个逻辑系统紧凑表示问题的能力。近年来关于简洁性的研究逐渐得到人们的关注。本文将讨论两类逻辑程序,即基数约束程序(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.