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

In this paper, it is shown that stable model semantics, perfect modelsemantics, and partial stable model semantics of disjunctive logicprograms have the same expressive power with respect to thepolynomial-time model-equivalent reduction. That is, taking perfect modelsemantics and stable model semantic as an example, any logic program Pcan be transformed in polynomial time to another logic program P' suchthat perfect models (resp. stable models) of P 1-1 correspond tostable models (resp. perfect models) of P', and the correspondence canbe computed also in polynomial time. However, the minimal modelsemantics has weaker expressiveness than other mentioned semantics,otherwise, the polynomial hierarchy would collapse to NP.