Determining Inference Semantics for Disjunctive Logic Programs (Extended Abstract)

1 Introduction

In a seminal paper, [Gelfond and Lifschitz, 1991] 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 GLsemantics) based on a program transformation (called GLreduct) and the minimal model requirement. Our observations reveal that the requirement of GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong and exclude some answer sets that would be reasonably acceptable, as illustrated in the following example.

Example 1. Consider the simple disjunctive program.

Intuitively, rule (1) presents two alternatives for answer set construction, namely a or b, and rules (2) and (3) infer b and c, respectively if a has already been derived. Rule (4) is a constraint stating that there is no answer set that does not contain c. We distinguish between the following two cases. Suppose that we choose a from rule (1); then by rules (2) and (3) we obtain a potential answer set I1 = {a, b, c}. I1 satisfies the constraint (4), so it is a candidate answer set for Π. Alternatively, suppose that we choose b from rule (1). As a is not inferred from rule (1), rules (2) and (3) are not applicable;

∗This paper is an extended abstract of the article [Shen and Eiter, 2019] in Artificial Intelligence, 277:1-28, 2019.

so rules (1), (2) and (3) together infer a potential answer set I2 = {b}. As I2 does not satisfy the constraint (4), it is not a candidate answer set for Π. Consequently, I1 = {a, b, c} is a minimal candidate answer set and thus we expect it to be an answer set of Π. However, I1 is not an answer set under GL-semantics because it is not a minimal model of Π.

To address this, we present a more permissive semantics:

(1) We present a general answer set semantics for disjunctive programs, called determining inference semantics (DI-semantics for short), which interprets the operator | in rule heads differently from the classical connective ∨, and does not require that answer sets should be minimal models. Specifically, we formalize the rule head operator | by introducing a head selection function sel , i.e., for every interpretation I and rule head H1 | · · · | Hk, sel(H1 | · · · | Hk, I) nondeterministically selects one alternative Hi satisfied by I. Then we define answer sets as follows: (i) Given an interpretation I and a selection function sel , we transform a disjunctive program Π into a normal program ΠIsel , called disjunctive program reduct, such that for every rule head(r) ← body(r) in Π, sel(head(r), I) ← body(r) is in ΠIsel if I satisfies body(r); (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set w.r.t. X if I is an answer set of ΠIsel under X; and (iii) we define I to be an answer set w.r.t. X if I is a minimal candidate answer set. Such answer sets are called DI-answer sets.

(2) By replacing the base semantics X in the above general semantics with the GLnlp-semantics defined by [Gelfond and Lifschitz, 1988], we induce a DI-semantics for simple disjunctive programs (definitions follow below). We show that an answer set under GL-semantics is an answer set under DI-semantics, but not vice versa; the main reason behind is that GL-semantics interprets the operator | in rule heads as the classical connective ∨ and further requires that answer sets must be minimal models; this may exclude some desired answer sets. To clearly see the essential difference of DIsemantics from GL-semantics, we also present a new characterization of GL-semantics in terms of a disjunctive program reduct ΠIsel . Based on this characterization, we obtain a satisfactory solution to an open problem of [Hitzler and Seda, 1999], which was to characterize split normal derivatives of a simple disjunctive program Π.

1. By replacing the base semantics X with the well-

justified semantics defined by [Shen et al., 2014], we further induce a DI-semantics for general disjunctive programs consisting of rules of the form H1 | · · · | Hk ← B, where B and every Hi are arbitrary first-order formulas. This closes the open issue of [Shen et al., 2014] how to extend the welljustified semantics from general normal programs with rules of the form H1 ← B to general disjunctive programs.

(4) Finally, we show that in the propositional case deciding whether a simple disjunctive program Π has some DIanswer set is NP-complete, and deciding whether a ground literal is true in some (resp. every) DI-answer set of Π is Σp2 -complete (resp. Πp2 -complete). This is in contrast to GLsemantics, where deciding whether a simple disjunctive program has GL-answer sets is Σp2 -complete [Eiter and Gottlob, 1995]. For general disjunctive programs, the complexity of DI-semantics increases to Σp2 -completeness for DI-answer set existence and to Σp3 -completeness and Πp3 -completeness for brave and cautious reasoning, respectively.

For an extensive discussion of historical and philosophical background, we refer to [Shen and Eiter, 2019].

2 Disjunctive Programs

We take a first-order logic language LΣ with equality. A firstorder theory (or theory) is a set T of closed formulas. By NΣ we denote the set of all ground (variable-free) terms of Σ, and by HΣ the set of all ground atoms. An interpretation I is a subset of HΣ such that for any ground atom A, I satisfies A if A ∈ I, and ¬A if A ̸∈ I. The notion of satisfaction/models of a formula/theory in I is defined as usual. A theory T entails a closed formula F, denoted T |= F, if all models of T are models of F. For an interpretation I, we let I - = HΣ \ I and ¬I - = {¬A | A ∈ I -}.

Definition 1. A general disjunctive program (disjunctive program for short) is a finite set of rules of the form

where k > 0, and B and the Hi's are first-order formulas.

For a rule r, we refer to B and H1 | · · · | Hk as its body and head, denoted body(r) and head(r), respectively. We also refer to each Hi as a head formula. A constraint is a rule of the form ⊥ ← B. A rule A ← ¬A amounts to a constraint ⊥ ← ¬A. A disjunctive program is a general normal program (normal program for short) if k = 1 for every rule; a simple disjunctive program if each Hi is an atom and B is a conjunction of literals, and a simple normal program if additionally k = 1. A positive simple normal/disjunctive program is a simple normal/disjunctive program without negative literals. The grounding of a disjunctive program Π, obtained by substituting the free variables in Π with constants in all possible ways, is denoted ground(Π).

An interpretation I satisfies a rule head H1 | · · · | Hk if it satisfies some Hi; I satisfies a rule r if it either satisfies head(r) or it does not satisfy body(r); I is a model of a disjunctive program Π if I satisfies every rule r ∈ ground(Π).

Let Π be a simple disjunctive program and I an interpretation. The GL-reduct of Π w.r.t. I, written as ΠI , is obtained from ground(Π) by (1) removing all rules whose bodies contain some ¬Ci with Ci ∈ I, and (2) removing from the remaining rules all ¬Ci. The GL-semantics defines I to be an answer set of Π (referred to as GL-answer set) if I is a minimal model of ΠI [Gelfond and Lifschitz, 1991]. When Π is a simple normal program, the GLnlp-semantics defines I to be an answer set of Π if I is the least model of ΠI . For simple normal programs, GL- and GLnlp-semantics coincide.

Remark 1. If we replace | with ∨ in rule heads and let ΠI∨ be ΠI with all occurrences of | replaced by ∨, then ΠI has the same minimal models as ΠI∨. Thus I is an answer set of Π under GL-semantics iff I is a minimal model of ΠI iff I is a minimal model of ΠI∨. This means that in GL-semantics the use of | in rule heads amounts in essence to disjunction ∨.

3 Determining Inference (DI) Semantics

Under the constructive view of the operator | as a nondeterministic inference operator, every rule head H = H1 | · · · | Hk in a disjunctive program can be viewed as a set {H1, · · · ,Hk} of alternatives. As these alternativesmay have different variants (i.e., every Hi can be expressed as different yet logically equivalent formulas) and appear in different orders in rule heads, we introduce a notion of variant rule heads.

Definition 2. Rule heads H1 = E1 | · · · | Ek and H2 = F1 | · · · | Fl, where the Ei's and Fj's are closed formulas, are variant rule heads if for every Ei in H1 some Fj in H2 exists with Ei ≡ Fj , and vice versa for every Fj in H2 some Ei in H1 exists with Ei ≡ Fj.

Intuitively, variant rule heads H1 and H2 represent the same set of alternatives and should be treated the same. If k > l, then H1 must have some head formulas that are logically equivalent. Moreover, rule heads in a simple disjunctive program are variant rule heads iff they have the same atoms.

Definition 3. Let Π be a disjunctive program and I the collection of all interpretations. Let HDΠ be the set of all rule heads in ground(Π), and HFΠ the set of all head formulas in HDΠ. A head selection for Π is a function sel : HDΠ×I → HFΠ ∪ {⊥} such that for every interpretation I ∈ I and every rule r ∈ ground(Π),

such that for every variant rule heads H1 and H2 in HDΠ, sel(H1, I) ≡ sel (H2, I).

A head selection function sel formalizes the operator | as a nondeterministic operator; i.e., for any interpretation I, sel(F1 | · · · | Fk, I) returns from a rule head F1 | · · · | Fk one of the alternatives Fi satisfied by I, or it returns ⊥ if there is no Fi that is satisfied by I. For variant rule heads, it returns logically equivalent alternatives that are satisfied by I.

Definition 4. Let Π be a disjunctive program, I an interpretation and sel a head selection function. The reduct of Π w.r.t. I and sel is ΠIsel = {sel(head(r), I) ← body(r) | r ∈ ground(Π) s.t. I satisfies body(r)}.

A reduct ΠIsel is a normal program; therefore we can apply any existing answer set semantics for normal programs to compute answer sets of ΠIsel . Intuitively I is a candidate answer set of Π if I is an answer set of ΠIsel , and I is an answer set of Π if I is minimal among all candidate answer sets.

Definition 5. Let I be a model of a disjunctive program Π, and X be an answer set semantics for normal programs. Then I is an answer set of Π w.r.t. X if (1) for some head selection function sel , I is an answer set of ΠIsel under X, and (2) Π has no model J ⊂ I satisfying condition (1).

Due to the use of head selection functions, the above semantics interprets the disjunctive rule head operator | differently from the classical connective ∨. Let H1 = E1 | · · · | Ek and H2 = E1 ∨ · · · ∨ Ek be two rule heads and let I be an interpretation that satisfies H2. Then there may be up to k head selection functions for H1, each selecting one alternative Ei that is satisfied by I, which leads to at most k disjunctive program reducts; in contrast, there is only one head selection function for H2, i.e., sel(H2, I) = H2, which leads to only one disjunctive program reduct. Different reducts may lead to different candidate answer sets and thus disjunctive programs with rule heads like H1 are different from programs with rule heads like H2.

Moreover, the above semantics does not require that answer sets should be minimal models; it only requires answer sets to be minimal among all candidate answer sets.

In order to stress the intuition that candidate answer sets are determined by means of a chosen head selection function for applying rules H1 | · · · | Hk ← Body, where one alternative Hi from the head is inferred when Body is satisfied, we refer to the above answer set semantics as determining inference (DI) semantics for disjunctive programs; we call answer sets of DI-semantics DI-answer sets and models satisfying condition (1) of Definition 5 candidate DI-answer sets.

4 DI-Semantics for Simple Disjunctive Programs

By replacing the base semantics X in Definition 5 with GLnlp-semantics we induce a DI-answer set semantics for simple disjunctive programs.

Definition 6. A model I of a simple disjunctive program Π is a DI-answer set of Π, if (1) for some head selection function sel , I is an answer set of ΠIsel under GLnlp-semantics, and (2) Π has no model J ⊂ I satisfying condition (1).

A DI-answer set is not necessarily a GL-answer set, but for simple normal programs and positive simple disjunctive programs, DI-semantics agrees with GL-semantics.

Theorem 1. Let Π be a simple normal program or a positive simple disjunctive program. Then an interpretation I is a DIanswer set of Π iff I is a GL-answer set of Π.

It is particularly interesting to observe that GL-semantics can also be characterized using the disjunctive program reduct ΠIsel of Definition 4 simply by requiring that for every (instead of some) head selection function sel , I is an answer set of ΠIsel under GLnlp-semantics. This reveals the essential difference between DI-semantics and GL-semantics.

Theorem 2. A model I of a simple disjunctive program Π is a GL-answer set of Π iff for every head selection function sel , I is an answer set of ΠIsel under GLnlp-semantics.

As GL-answer sets of a simple disjunctive program Π are minimal models of Π, the following corollary is immediate.

Corollary 1. Let Π be a simple disjunctive program. If I is a GL-answer set, then I is a DI-answer set.

5 DI-Semantics for General Programs

General normal programs consist of rules of the form H ← B, where H and B are first-order formulas. To overcome the problem of circular justifications with those answer set semantics for general normal programs such as those in [Pearce, 2006; Truszczynski, 2010; Bartholomew et al., 2011; Faber et al., 2011; Ferraris et al., 2011] based on classical logic, [Shen et al., 2014] presented the well-justified semantics whose answer sets have a level mapping and thus are free of circular justifications, in analogy to the level mapping of GLnlpsemantics for simple normal programs [Fages, 1994]. [Shen et al., 2014] left extending the well-justified semantics to general disjunctive programs as an open problem; we can elegantly close it by replacing the base semantics X in Definition 5 with the well-justified semantics.

The well-justified semantics is based on the one-step provability operator TΠ(O,N), which extends the well-known immediate consequence operator [van Emden and Kowalski, 1976] from Horn programs to general normal programs.

Definition 7 ([Shen et al., 2014]). Let Π be a general normal program, and let O and N be two first-order theories. Then

Informally, TΠ(O,N) collects all heads of grounded rules whose bodies are entailed by O ∪N. For fixed N, the entailment |= is monotone in O, so TΠ(O,N) is monotone w.r.t. O, i.e., for any theories O1 ⊆ O2, we have TΠ(O1,N) ⊆ TΠ(O2,N). As moreover TΠ(O,N) is finitary, the inference sequence 〈T iΠ(∅, N)〉∞i=0 , where T 0Π(∅, N) = ∅ and for i ≥ 0 T i+1 Π (∅,N) = TΠ(T iΠ(∅,N),N), will converge to a least fixpoint, denoted lfp(TΠ(∅,N)).

The well-justified (WJ) semantics is then defined in terms of lfp(TΠ(∅, ¬I -)), i.e., derivability under the closed-world assumption applied to candidate answer I, as follows.

Definition 8 ([Shen et al., 2014]). Let I be a model of a general normal program Π. Then I is a WJ-answer set of Π if lfp(TΠ(∅, ¬I -)) ∪ ¬I - |= A for every A ∈ I.

By replacing X in Definition 5 with WJ-semantics we induce a DI-answer set semantics for general programs.

Definition 9. Amodel I of a general disjunctive programΠ is a DI-answer set of Π if (1) for some head selection function sel , I is a WJ-answer set of ΠIsel , and (2) Π has no model J ⊂ I satisfying condition (1).

Intuitively, a DI-answer set is a model that is minimal among all models that can be nondeterministically (by means of a head selection function) inferred by iteratively applying rules via a bottom up fixpoint sequence.

Corollary 2. For a general normal program, I is a DIanswer set iff I is a WJ-answer set. For a simple disjunctive program, I is a DI-answer set under Definition 9 iff I is a DI-answer set under Definition 6.

6 Computational Complexity

We address the computational complexity of propositional logic programs, where we focus on the DI-semantics with the well-justified semantics [Shen et al., 2014] as the base semantics and refer to it as DI-WJ answer set semantics.

Theorem 3. Given a propositional simple (resp. general) disjunctive program Π and a ground literal L, deciding whether (i) Π has some DI-WJ answer set is NP-complete (resp. Σp2 - complete), (ii) L is true in every DI-WJ answer set of Π is Πp2 -complete (resp. Πp3 -complete), and (iii) L is true in some DI-WJ answer set of Π is Σp2 -complete (resp. Σp3 -complete).

Analogous results hold for other semantics such as FLPsemantics [Faber et al., 2011]. Compared to GL-/FLPsemantics, the complexity of brave and cautious reasoning increases under DI-semantics by one level of PH, thus offering higher problem solving capacity. Computing a DI-WJ answer set is complete for the NP- resp. Σp2 -functions and feasible with bounded many witness oracle calls [Buss et al., 1993; Janota and Marques-Silva, 2016] in polynomial time.

7 Difference between Disjunctive Rule Heads and Choice Constructs

Like disjunctive rule heads, choice constructs [Simons et al., 2002; Ferraris and Lifschitz, 2005; Calimeri et al., 2012] are also used to express a set of alternatives. However, a disjunctive rule head a1 | · · · | am and a choice construct of the form u1{a1, · · · , am}u2, where m > 0, 0 ≤ u1 ≤ u2 ≤ m, and the ai's are ground atoms, are essentially different.

Let α={a1, · · · , am} and β={γ | γ ⊆ α and u1 ≤ |γ| ≤ u2}. The choice construct u1{a1, · · · , am}u2 says that any γ ∈ β can be chosen as answer.

For a logic program Π, let AS(Π) denote the set of answer sets of Π. Let Π′ be Π extended with a choice construct u1{a1, · · · , am}u2. Then the set of answer sets of Π′ is

Example 2. Let Π = {b} and Π′ = Π ∪ {1{a, b}2}. Then AS(Π′ ) = AS(Π ∪ {a, ¬b}) ∪ AS(Π ∪ {¬a, b}) ∪ AS(Π ∪ {a, b}). Π ∪ {a, ¬b} has no model and thus no answer set, Π ∪ {¬a, b} has a single answer set {b}, and Π ∪ {a, b} has a single answer set {a, b}. Therefore, Π′ has in total two answer sets, {b} and {a, b}.

A disjunctive rule head a1 | · · · | am infers one atom ai from α and differs essentially from a choice construct 1{a1, · · · , am}u. When u = 1, the choice construct 1{a1, · · · , am}1 in a logic program Π enforces every answer set of Π to contain exactly one ai from α. In contrast, though a1 | · · · | am infers only one ai from α, a DI-answer set may contain other atoms aj ∈ α, which are inferred by other rules in a disjunctive program. When u > 1, the choice construct 1{a1, · · · , am}u allows for answer sets I and J with I ⊂ J. This will not happen with a1 | · · · | am for DI-answer sets.

8 Relation to Split and Fork Programs

For simple disjunctive programs Π, [Hitzler and Seda, 1999] proposed to split Π into a collection of simple normal programs, called normal derivatives P(Π), which informally are obtained from ground(Π) by replacing every rule A1| · · · |Ak ← body(r), k ≥ 2, arbitrarily with one or more rules Ai ← body(r), 1 ≤ i ≤ k. E.g., Π = {p | q ← ¬s} has three normal derivatives: P1(Π) = {p ← ¬s}, P2(Π) = {q ← ¬s}, and P3(Π) = {p ← ¬s, q ← ¬s}.

[Hitzler and Seda, 1999] aimed to use normal derivatives to characterize GL-semantics of a simple disjunctive program Π. They showed that every answer set of Π under GLsemantics is an answer set of some normal derivative of Π under GLnlp-semantics. E.g. for the program Π from above, I = {p} is an answer set of Π under GL-semantics and an answer set of P1(Π) under GLnlp-semantics. However, they left a precise characterization open, stated as the problem to determine for every interpretation I some normal derivatives such that I is an answer set of Π under GL-semantics iff I is an answer set of these normal derivatives under GLnlp-semantics.

The characterization of GL-semantics by the disjunctive program reduct (Theorem 2) enables us to provide a solution for this open problem. For a logic program Π, an interpretation I and a head selection sel on I, let

Note that ND(Π, I) is the collection of normal derivatives obtained by applying every head selection on I. Thus for any head selection sel on a model I, we have

and body(r) is not satisfied by I}.

A solution to the above open problem is then as follows.

Theorem 4. An interpretation I is an answer set of a simple disjunctive program Π under GL-semantics iff I is an answer set of every P(Π) ∈ND(Π, I) under GLnlp-semantics.

In independent work and parallel to ours, [Aguado et al., 2019] proposed a new construct "|" for answer programs called fork, which aims at overcoming problems with omitting auxiliary atoms in choice constructs. Informally, under fork semantics the answer sets of {E |F} ∪ Π are the answer sets of {E}∪Π plus the answer sets of {F}∪Π. Accordingly, P = {a | b, b | c} has the fork-answer sets {a, b}, {a, c}, {b} and {b, c}, while its DI-answer sets are {a, c} and {b}. They diverge as DI-semantics operates in a sense globally on alternatives in different rules (by item (2) in Definition 5), while fork semantics operates locally treating them independently.

Notably, selection functions similar to ours were used in [Vennekens et al., 2004] to define probabilistic semantics for logic programs with annotated disjunctions. However, they do not depend on an interpretation and result (disregarding probabilities) in all normal derivatives picking always a single rule Ai ← body (in the example, P1(Π) and P2(Π)). Thus like fork semantics, this semantics has a local flavor.

Acknowledgments

This work has been supported in part by NSFC grants 61976205 and 61379043, and the Austrian Science Fund (FWF) grant P27730.