APP下载

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

2016-10-09张燕

逻辑学研究 2016年2期
关键词:程序规则

张燕

中山大学逻辑与认知研究所

zhang85@mail2.sysu.edu.cn

沈榆平

中山大学逻辑与认知研究所

shyping@mail.sysu.edu.cn

赵希顺

中山大学逻辑与认知研究所

hsszxs@mail.sysu.edu.cn



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

张燕

中山大学逻辑与认知研究所

zhang85@mail2.sysu.edu.cn

沈榆平

中山大学逻辑与认知研究所

shyping@mail.sysu.edu.cn

赵希顺

中山大学逻辑与认知研究所

hsszxs@mail.sysu.edu.cn

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

简洁性;回答集;基数约束程序;前提嵌套程序

1 引言

逻辑系统的简洁性指该系统紧凑表示问题的能力。简单地说,对于系统C 和C′,若C′中的每个理论都可等价翻译(不添加辅助变元)为C中的理论而不会引起该理论长度的指数增长,则称C至少与C′一样简洁(C′≾C)。最近,对基于回答集语义的逻辑程序(Answer Set Programs,ASP,[1,5,7])的简洁性研究已经引起领域内的兴趣。([8,12])ASP是处理规划、诊断、常识推理等应用的一种人工智能逻辑,它包括许多子类,如基数约束程序(Cardinality Constraint Programs,CCP,[3])、前提嵌套程序(Nested Logic Programs,NLP,[9])等。人们已经知道CCP和NLP有相同的表达能力(它们与命题逻辑等价)和推理复杂性(一致性检测为NP-完全,[3,9,12]),但它们之间的相对简洁性尚无明确结论。

本文将证明CCP≾NLP,即NLP至少与CCP一样简洁,或者说,每一个CCP程序都可以等价翻译为一个多项式长度的NLP程序。具体……

登录APP查看全文

猜你喜欢

程序规则
撑竿跳规则的制定
数独的规则和演变
试论我国未决羁押程序的立法完善
规则的正确打开方式
失能的信仰——走向衰亡的民事诉讼程序
让规则不规则
“程序猿”的生活什么样
英国与欧盟正式启动“离婚”程序程序
TPP反腐败规则对我国的启示
搜索新规则