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

摘要

直观地说,简洁性是指一个逻辑系统紧凑表示问题的能力.近年来关于简洁性的研究逐渐得到人们的关注.本文将讨论两类逻辑程序,即基数约束程序(Cardinality Constraint Programs,CCP)与前提嵌套程序(Nested Logic Programs,NLP)之间的简洁性.我们设计了一个从CCP到NLP多项式长度的等价翻译,这极大改进了Ferraris和Lifschitz提出的指数长度翻译方法,由此证明NLP至少与CCP一样简洁.