Determining inference semantics for disjunctive logic programs
Yi-Dong Shen, Thomas Eiter · Artificial Intelligence · 2019
In a seminal paper, Gelfond and Lifschitz [34] introduced simple disjunctive logic programs, where in rule heads the disjunction operator “|” is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct ) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics . Specifically, we introduce a head selection function to formalize the operator | and define answer sets as follows: (i) Given an interpretation I and a selection function sel , we transform a disjunctive program Π into a normal program Π s e l I , called a disjunctive program reduct ; (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set of Π w.r.t. X if I is an answer set of Π s e l I under X ; and (iii) we define I to be an answer set of Π w.r.t. X if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics X for normal programs to disjunctive programs. By replacing X with the GL n l p -semantics defined by Gelfond and Lifschitz [33] , we induce a DI-semantics for simple disjunctive programs, and by replacing X with the well-justified semantics defined by Shen et al. [65] , we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda [36] about characterizing split normal derivatives of a simple disjunctive program Π such that answer sets of the normal derivatives are answer sets of Π under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Π has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics [24] , where deciding whether Π has some answer set is Σ 2 p -complete, while brave and cautious reasoning are Σ 2 p - and Π 2 p -complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity.