Reducing disjunctive to non-disjunctive semantics by shift-operations

It is wellknown that Minker's semantics GCWA for positive disjunctive programs P is #PI#_2"P-complete, i.e. to decide if a literal is true in all minimal models of P. 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_p"s"u"p"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 the authors and Marco 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, and Walker's stratified semantics M_P"s"u"p"p and of Van Gelder, Ross, and Schlipf's wellfounded 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_P"s"u"p"p is not always defined: testing consistency of Weak-M_P"s"u"p"p is also NP-complete. We also show that Weak-WFS and Weak-M_P"s"u"p"p are cumulative (but not rational) and that, in addition. Weak-WFS satisfies some of the well-behaved principles introduced by Dix. (orig.)Available from TIB Hannover: RO 6844(1995,18) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman