Reducing Disjunctive to Non-Disjunctive Semantics by Shift-Operations

Abstract

It is wellknown that Minker's semantics GCWA for positive disjunctive programs P, i.e. to decide if a literal is true in all minimal models of P is Π^P₂-complete. This is in contrast to the same entailment problem for semantics of non-disjunctive programs such as STABLE and SUPPORTED (both are co-NP-complete) as well as M^supp_P and WFS (that are even polynomial). Recently, the idea of reducing disjunctive to non-disjunctive programs by using so called shift-operations was introduced independently by Bonatti, Dix/Gottlob/Marek, and Schaerf. In fact, Schaerf associated to each semantics SEM for normal programs a corresponding semantics Weak-SEM for disjunctive programs and asked for the properties of these weak semantics, in particular for the complexity of their entailment relations. While Schaerf concentrated on Weak-STABLE and Weak-SUPPORTED, we investigate the weak versions of Apt/Blair/Walker's stratified semantics M^supp_P and of Van Gelder/Ross/Schlipf's well-founded semantics WFS. We show that credulous entailment for both semantics is NP-complete (consequently, sceptical entailment is co-NP-complete). Thus, unlike GCWA, the complexity of these semantics belongs to the first level of the polynomial hierarchy. Note that, unlike Weak-WFS, the semantics Weak-M^supp_P is not always defined: testing consistency of Weak-M^supp_P is also NP–complete. We also show that Weak-WFS and Weak-M^supp_P are cumulative and rational and that., in addition, Weak-WFS satisfies some of the well-behaved principles introduced by Dix.