CHARACTERIZATIONS OF THE DISJUNCTIVE STABLE SEMANTICS BY PARTIAL EVALUATION

There are three most prominent semantics defined for certain subclasse s of disjunctive logic programs: GCWA (for positive programs), PERFECT (for stratified programs), and STABLE (defined for the whole class of all disjunctive programs). While there are various competitors based on 3-valued models, notably WFS and its disjunctive counterparts, ther e are no other semantics consisting of two-valued models. We argue tha t the reason for this is the Partial Evaluation property (also called Unfolding or Partial Deduction) well known from logic programming. In fact, we prove characterizations of these semantics and show that if a semantics SEM satisfies Partial Evaluation and Elimination of Tautolo gies, then (1) SEM is based on two-valued minimal models for positive programs, and (2) if SEM satisfies in addition Elimination of Contradi ctions, it is based on stable models. We also show that if we require Isomorphy and Relevance, then STABLE is completely determined on the c lass of all stratified disjunctive logic programs. (C) Elsevier Scienc e Inc., 1997.