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

摘要：

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

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

所属期刊栏目：9

分类号：B81(逻辑学(论理学))

资助基金：国家社会科学基金青年项目《逻辑系统的简洁性研究》14CZX058

在线出版日期：2017-03-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共18页

页码：14-31