前提嵌套程序和基数约束程序的简洁性研究
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 一样简洁。