Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction  

作　　者：赵希顺 沈榆平 

机构地区：[1]Institute of Logic and Cognition,Sun Yat-Sen University

出　　处：《Journal of Computer Science & Technology》2007年第4期562-568,共7页计算机科学技术学报（英文版）

基　　金：This research was partially supported by the National Natural Science Foundation of China under Grant Nos.60573011,10410638;an MOE Project of Key Institute at Universities under Grant No.05JJD72040122.

摘　　要：In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.

关 键 词：disjunctive logic program SEMANTICS polynomial-time model-equivalent reduction quantified Boolean formula 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]