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 mode...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 we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence in NP.It is shown that among all NP-systems with model checking problem i...In this paper we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence in NP.It is shown that among all NP-systems with model checking problem in NP,the existentially quantified propositional logic（PF） is maximal with respect to poly-time model-equivalent reduction.However,PF seems not a maximal NP-system in general because there exits an NP-system with model checking problem DP-complete.展开更多
基金This research was partially supported by the National Natural Science Foundation of China under Grant Nos.60573011,10410638an 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.
基金supported by the National Natural Science Foundation of China under Grant No.60970040Ministry of Education,Key Research Projects of Philosophy and Social Science under Grant No.05JJD72040122the Sun Yat-Sen University Young Scholar Project
文摘In this paper we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence in NP.It is shown that among all NP-systems with model checking problem in NP,the existentially quantified propositional logic（PF） is maximal with respect to poly-time model-equivalent reduction.However,PF seems not a maximal NP-system in general because there exits an NP-system with model checking problem DP-complete.
