Disjunction in knowledge representation concisely expresses uncertainty as sets of possibilities. Due to the nondeterministic nature of these sets, we require specialized tools to establish the meaning of languages that incorporate disjunction. In this work, we further prove the efectiveness of one such tool: Our recent extension of approximation fixpoint theory (AFT) to disjunctive semantics. This approach has the advantage of simplicity because it directly utilizes the existing objects and definitions of AFT. To exercise our approach, we capture the determining inference semantics of Shen and Eiter, a class of disjunctive semantics where any non-disjunctive answer set semantics is extended to disjunctive logic programs. This leads to a fixpoint characterization of this class of disjunctive semantics. Additionally, we extend determining inference semantics to the three-valued case. In the case of disjunctive logic programs, we combine the determining inference stable models with partial stable models. A combination of these semantics that is faithful presents a challenge due to incompatibility concerning truth minimality. However, due to the flexibility of our approach, we are able to remedy this challenge by introducing a new truth ordering.
Approximation fixpoint theory [
Using a family of operators has a few interesting benefits. Firstly, the definitions and objects of
deterministic AFT can be directly reused in this lifted theory. Unlike nondeterministic AFT [
By parameterizing this merge operation, the approximator set approach is highly flexible and a question is raised of what other disjunctive semantics we can capture with this approach. In this work, we show that we can capture the determining inference semantics of disjunctive logic programs by tweaking the merge operation for the set of operators for partial stable models. The relative ease with which this is accomplished further supports our approach.
Shen and Eiter [
←
, ←
←
We can separate the program into two non-disjunctive programs: (a) one which replaces , ← with
← , efectively “choosing” the atom , and (b) the program which “chooses” . Under ℳ semantics,
program (a) does not have an answer set and program (b) has a single answer set {, } which assigns
both and to be true. Disjunction in DLPs is not equivalent to disjunction in classical logic [
This paper reports the results of our investigation, and the main contributions are as follows:
1. Under reasonable syntactic restrictions, we successfully apply approximator sets [
The paper is organized as follows. In Section 2, we cover the necessary preliminaries and establish notation for disjunctive logic programs (Section 2.1), approximation fixpoint theory (Section 2.2), and determining inference semantics (Section 2.3). In Section 3 we apply approximator sets to determining inference semantics and establish a three-valued semantics. Finally, we conclude and discuss in Section 4.
A disjunctive logic program (DLP) is a set of rules. Each rule ∈ consists of a set of atoms called its head, denoted ℎ(), and a set of possibly negated atoms called its body, denoted (). A rule with the parts ℎ() = {ℎ1, . . . , ℎ} ̸= ∅ and () = {1, . . . , , 1, . . . , } is written as ℎ1, . . . , ℎ ← 1, . . . , , 1, . . . , . For such a rule , we also define +() := {1, . . . , } and − () := {1, . . . , } to extract the positive body and the negative body of the rule. Note that the elements in − () are atoms rather than negated atoms. We say a rule is normal if there is exactly one atom in ℎ(). A program that only contains normal rules is a normal program (a non-disjunctive program).
In this work, without loss of generality, we do not consider logic programs with variables. That is, we assume every program is variable-free or ground.
An interpretation of a DLP is a true/false assignment to every atom that appears in . A set of atoms is an interpretation that assigns its contained atoms to be true and all other atoms to be false. We also consider three-valued interpretations represented by pairs of sets of atoms (described later). When it is necessary to disambiguate between types of interpretations, we call them two-valued interpretations or three-valued interpretations.
Gelfond and Lifschitz [
defined as := {ℎ() ← +() | ∈ , − () ∩ = ∅}. A rule is satisfied by if ((+() ⊆ ) ∧ (− () ∩ = ∅)) =⇒ (ℎ() ⊆ ) is true. An interpretation is a model of if every rule is satisfied by . A model of is an answer set of if there does not exist a model ′ of s.t. ′ ⊂ .
Przymusinski [
We briefly summarize the four-valued logic given by Belnap and Nuel [
The truth-ordering places at the top, at the bottom, and and are incomparable. The precisionordering places at the top, at the bottom, while and are incomparable.
We formulate a four-valued interpretation as a pair of sets ( , ) where and are interpretations. A valuation ( , )() of an atom against an interpretation ( , ) is if ∈ ∩ , if ̸∈ ∪ , if ̸∈ , ∈ , and if ∈ , ̸∈ . The set contains true atoms, while contains possibly true atoms (either true or undefined) while the set ∖ contains all contradictory atoms. False atoms are not contained in either set or . We say such an interpretation is consistent (three-valued) if ⊆ . We call an interpretation ( , ) exact or two-valued.
We define the truth-ordering ( ⪯ 2 ) and precision-ordering (⪯ 2) for interpretations as follows. Definition 2.
For two interpretations ( , ) and ( ′, ′) ( , ) ⪯ 2 ( ′, ′) ⇐⇒ ⊆ ′ and ⊆ ′ ( , ) ⪯ 2 ( ′, ′) ⇐⇒ ⊆ ′ and ′ ⊆
Intuitively, these orderings relate interpretations whose individual atom valuations relate according to Belnap’s logic. With ( , ) ⪯ 2 ( ′, ′), we have ⊆ ′ where and ′ contain the set false of atoms in ( , ) and ( ′, ′) respectively. We use the following to relate rules and interpretations by describing the set of rules whose bodies are satisfied by an interpretation.
(, )( ) := { ∈ | +() ⊆ , − () ∩ = ∅} Given a consistent ( , ), we say a rule ’s body is satisfied by ( , ) if ∈ (, )({}).
With slight abuse of notation, we use ℎ( ) (normally ℎ() with a particular rule ) to denote the set of atoms that appear in the heads of rules in a normal program . That is, ℎ( ) := {ℎ() | ∈ }.
We adopt the method of Killen et al. [
Given a DLP , the set ( ) is defined as follows ( ) := {︁ {ℎ() | ∈ } | ∃ℎ, ∀ ∈ , ∃ ∈ ℎ(), ℎ() = ( ← ())}︁
For example, ({, ←} ) = {{ ←} , { ←}} . The programs completion for disjunctive
programs shows us that we can deal with disjunctive programs by treating the normal programs in the
set above [
Definition 4.
We call a consistent interpretation (, ) a model of a DLP if for some ′ ∈ () (ℎ((, )(′)), ℎ((, )(′))) ⪯ 2 (, ) We say a consistent ( ′, ′) is a model of the reduct of w.r.t. (, ) if for some ′ ∈ () (ℎ(( ′, )(′)), ℎ(( ′, )(′))) ⪯ 2 ( ′, ′) A model (, ) of a DLP is a ℳ answer set of if there does not exist ( ′, ′) ≺ 2 (, ) s.t. ( ′, ′) is a model of the reduct of w.r.t. (, ).
Przymusinski [
Approximation Fixpoint Theory (AFT) [
First, we introduce some lattice theory fundamentals for notation [
Given an ordering ⟨ℒ, ⪯⟩ and a function : ℒ → ℒ, we say that is monotone if ⪯ implies
() ⪯ (). We use ℒ2 to denote the set of pairs {(, ) | , ∈ ℒ}. For a function : ℒ2 → ℒ2, we
use (, )1 and (, )2 to project the first and second elements, respectively, of the resulting pair. We
partially apply and project such functions using the notation (· , )1 and (, · )2 to construct the new
unary functions , (, )1 and , (, )2 respectively. A fixpoint of a function is an element
such that () = . We use fix to denote the set of all fixpoints of . We use lfp to denote the least
ifxpoint of a function , that is, lfp := ⋀︀( fix ). If a function is monotone over a complete lattice,
then lfp is well-defined [
AFT [
function.
An approximator may have fixpoints that do not correspond to the intended semantics. The stable revision operator is formed from an approximator and has fewer fixpoints.
Definition 6.
Given an an approximator , its stable revision operator () is
() := (lfp (· , )1, lfp (, · )2)
Denecker et al. [
We introduce Shen and Eiter’s [
Definition 7. Given a DLP , a head selection function ℎ(, ) is a function that accepts an interpretation and a rule ∈ and returns an element ℎ ∈ ℎ() ∩ , unless ℎ() ∩ = ∅ in which case it returns ⊥.
Shen and Eiter impose an additional constraint requiring that for any two rules , ′ ∈ s.t. ℎ() = ℎ(′), then ℎ(, ) = ℎ(, ′). This choice appears to be made to accommodate their more generalized semantics that allow arbitrary formulas in the heads of rules. For simplicity, we do not consider arbitrary formulas and we do not explore this diference, and in the remainder of this work, we assume ℎ() ̸= ℎ(′) when ̸= ′ and |ℎ()| > 1. This is not so limiting as the semantics of an excluded program can be mimicked by adding fresh atoms to the head of each disallowed rule and additional rules that result in every atom being true if one of these atoms is selected from the head of a rule1. Without this syntactic restriction, we cannot establish a strong relationship between Shen and Eiter’s determining inference semantics and ℳ answer sets. However, if this restriction is removed, this work holds over a slightly modified version of determining inference semantics, which we soon describe. We leave a deeper investigation into this detail for future work.
From a head-selection function, normal programs are obtained as a disjunctive reduct. Definition 8. A disjunctive reduct ′ of a DLP w.r.t. an interpretation and a head selection function ℎ is a normal program such that ′ = {ℎ(, ) ← () | ∈ , satisfies ()}.
Soon, we will define a simpler version of the disjunctive reduct that does not involve an interpretation. We introduce determining inference semantics, which is parameterized by a semantics for normal logic programs. An answer set semantics for normal programs identifies a subset of models of normal programs as -answer sets s.t. they are truth-minimal.
Definition 9. Given an answer set semantics for normal programs, a model of a DLP is a DI- (determining inference ) answer set of if 1. is an -answer set of some disjunctive reduct of w.r.t. and some head selection function, and 2. there is no model of ′ ⊂ that satisfies (1).
It is convenient for us to make a few simplications and generalizations to Definition 9. We rely
on () (Definition 3) instead of interpretations in disjunctive reducts. Every model of a
′ ∈ () is a model of the DLP [
A DI-structure ⟨ , ⟨ℒ, ⪯⟩⟩ is an answer set semantics and an ordering ⟨ℒ, ⪯⟩ . The ordering, an interpretation structure, is used identify elements in ℒ as models of specific normal programs with some being -answer sets.
Definition 10. A (generalized) DI- semantics is given by a DI-structure ⟨ , ⟨ℒ, ⪯⟩⟩ . We say ∈ ℒ is a (generalized) DI- answer set of a DLP if 1. is an -answer set of some ′ ∈ (), and 2. there is no ′ ∈ ℒ s.t. ′ ≺ and ′ satisfies (1).
Proposition 1. Using the DI-structure ⟨ , ⟨ℐ, ⊆⟩⟩ , Definitions 9 and 10 are equivalent for programs s.t. for every rule ∈ with |ℎ()| > 1, there does not exist ′ ∈ s.t. ̸= ′ and ℎ() = ℎ(′). Proof. If is an answer set of a program ′ ∈ (), then we can construct a head selection function that chooses the true atoms from the heads of rules in ′. Removing the rules whose bodies are not satisfied by does not afect the status of as an answer set.
Clearly we have ′ ∈ () s.t. ′ has an answer set ′ ⊂ if there exists a disjunctive reduct that corresponds to ′. Note that head selection function for ′ uses ′, not , thus the removal of unsatisfied rules has no bearing on ′’s status as an answer set of ′.
From here on, we adopt Definition 10 for DI- semantics.
1While one might wish to use a constraint instead of making every atom true, under determining inference semantics, adding
constraints can introduce new answer sets [
Definition 11. The semantics DI-ℳ are given by applying DI- to Gelfond and Lifschitz’s answer set semantics (Definition 1) using the the DI-structure ⟨ℳ, ⟨ℐ, ⊆⟩⟩ .
We return to Shen and Eiter’s example [
We are now ready to capture determining inference semantics with approximator sets. First, we capture the semantics defined by Shen and Eiter, that is, the two-valued determining inference semantics. We show that given any two-valued answer set semantics , we can capture the two-valued DI- semantics using approximator sets.
First, we introduce approximator sets [
An approximator set is a finite 2 set of approximators.
To capture the DI semantics in the two-valued case, we can simply isolate the truth-minimal stable ifxpoints of approximators in an approximator set. Recall that we use fix (ℎ) to denote stable fixpoints of the approximator ℎ.
Definition 13. The exact DI- stable fixpoints of an approximator set are contained in the set ⪯ 2 (⋃︁{(, ) ∈ ifx ((ℎ)) | ℎ ∈ }) It is immediate that every exact DI- stable fixpoints is ⪯ 2 -minimal.
We now show how the above use of approximator sets can capture the DI- semantics for an answer set semantics . Given a semantics for normal programs and a DLP , an exact corresponding approximator set is a set of cardinality |()| s.t. for each ′ ∈ (), there is an approximator in whose exact stable fixpoints correspond to the -answer sets of ′. Theorem 1. Given an answer set semantics , a DLP , and an exact corresponding approximator set , we have that (, ) is an exact DI- stable fixpoint of (Definition 13) if it is an DI- answer set of (Definition 10) under a two-valued DI-structure ⟨ , ⟨ℐ, ⪯⟩⟩ .
Proof. (⇒) By definition, there is no approximator ℎ′ ∈ s.t. ( ′, ′) ∈ ifx (ℎ′ ) and ′ ⊂ . Thus, there is no ′ ∈ () with such an answer set ′. (⇐) Similarly, with no ′ ∈ () with an answer set ′ ⊂ , there is no ℎ ∈ with the exact stable fixpoint ( ′, ′).
Intuitively, if a two-valued non-disjunctive semantics has an approximator, then we can immediately derive a two-valued determining inference semantics to handle the disjunctive case.
For example, to capture determining inference semantics for Gelfond and Lifschitz’s answer set
semantics using stable revision, we adopt the approximator set defined for a set of normal programs by
Killen et al. [
Definition 14.
Given a DLP , Γ (, ) := {ℎ | ℎ() = {ℎ}, ∈ , +() ⊆ , − () ∩ = ∅} ℎ (, ) := (Γ (, ), Γ (, )) () := {ℎ′ | ′ ∈ ()} () is an approximator defined with the approximators that capture the ℳ semantics of the programs in (). The following comes immediately from Theorem 1 and because () is a corresponding approximator set for ℳ semantics.
Theorem 2. Let be an interpretation of a DLP . It is a DI-ℳ of if and only if (, ) is an exact DI-ℳ stable fixpoint of ().
We have established that we can use AFT to capture the Shen and Eiter’s [
AFT distinguishes two types of fixpoints that always exist, exhibit special properties, and that can be used to characterize new or existing semantics.
is the well-founded fixpoint of .
Several properties of the above can easily be shown due to the algebraic nature of fixpoints. Namely, that the Kripke-Kleene fixpoint is less than any other fixpoint, the well-founded fixpoint is less than any other stable fixpoint, and the Kripke-Kleene fixpoint is less than the well-founded fixpoint.
We now lift Kripke-Kleene and well-founded fixpoints to approximator sets.
Definition 16. For an approximator set , a • local Kripke-Kleene fixpoint of is a Kripke-Kleene fixpoint of some approximator from , and a • local well-founded fixpoint of is a well-founded fixpoint of some approximator from . Definition 17. For an approximator set , its global Kripke-Kleene (resp. global well-founded) fixpoints are ⪯ 2 -minimal local Kripke Kleene (resp. well-founded) fixpoints of .
The following comes immediately due to the finitude of an approximator set and the complete lattice
structure of ⪯ 2 [
Lemma 1. Every approximator set has at least one global Kripke-Kleene fixpoint and at least one global well-founded fixpoint.
In a similar vein to Heyninck et al. [
Definition 18. The Kripke-Kleene state (resp. well-founded state) of an approximator set is a nonempty set containing all of its global Kripke-Kleene fixpoints (resp. global well-founded fixpoints).
The existence of these states follows immediately from Lemma 1.
Corollary 1. For an approximator set , its Kripke-Kleene state (resp. well-founded state) is unique and nonempty.
We briefly instantiate the discussed definitions in the following example.
Example 2. Let ℒ = {⊥, ⊤, , } be the complete lattice where ⊥ ⪯ ⪯ ⊤ and ⊥ ⪯ ⪯ ⊤ . Define to be a set of approximators indexed by ℒ ∖ {⊥} such that for ∈ (ℒ ∖ {⊥}) and ℎ ∈ ℎ (, )1 := ⋁︁{, } ℎ (, )2 := ℎ (, )1
(, ⊤) is the Kripke-Kleene fixpoint and (, ) is the well-founded fixpoint. Clearly (, ⊤) ⪯ 2 (, ). These are local Kripke-Kleene (resp. well-founded) fixpoints of . The Kripke-Kleene state of is {(, ⊤), (, ⊤)} and the well-founded state of is {(, ), (, )}. If we were to add ℎ⊥ to , then its Kripke-Kleene state would be {(⊥, ⊤)} and its well-founded state would be {(⊥, ⊥)}.
For exact DI- stable fixpoints (Definition 13) we only minimize against exact stable fixpoints. However, our approximators for DI-ℳ semantics have stable fixpoints that are not exact. These partial stable ifxpoints are meaningful because they approximate exact stable fixpoints (like well-founded models). Our goal is to combine determining inference semantics with the partial stable model semantics to obtain a new semantics, DI- ℳ. If we minimize ℳ answer sets using the ⪯ 2 ordering, we do not preserve DI- ℳ answer sets. We briefly demonstrate how using ⪯ 2 , that is, the DI-structure ⟨ ℳ, ⟨ℒ2, ⪯ 2 ⟩⟩, is problematic.
Example 3. Let be the program from Example 1.
←
There is one ℳ answer set ({}, {, }) under Przymusinski’s semantics [
We wish to preserve both the DI-ℳ answer sets and Przymusinski’s ℳ answer sets. One
possible approach would be to remove every instance from the relation ⪯ 2 that compares exact pairs
with non-exact pairs. This technique is employed by Knorr et al. [
However, the approach of modifying ⪯ 2 in this way yields an unnatural semantics. One simply has to add the rule ← to a program (where is a fresh atom), ignore in the resulting interpretations, and the resulting semantics are equivalent having used ⪯ 2 in the DI-structure. Later on, we demonstrate this concretely in Example 4. To address this peculiarity, we introduce a new ordering for truth-minimization.
Definition 19.
(, ) ⪯ 2 (′, ′) ⇐⇒ ⪯ ′ and ⪯ (′ ∖ (′ ∖ )) Note that because the underlying ordering is ⊆ , the ∖ operation is defined as the set diference.
2 Intuitively, ⪯ exhibits a quasi-truth ordering in that it removes certain pairings from the relation that compare exact pairs with non-exact pairs. Additionally, ⪯ 2 compares truth values of individual atoms in a way that resembles ⪯ 2 , with the diference that the values and are incomparable. That is, for an answer set to be favoured over another, it must make some true or undefined atoms false. In contrast to ⪯ 2 , in which to shrink an interpretation, it is suficient to assign some true atoms the value of undefined.
First, we show that this new ordering is weaker than ⪯ 2 .
Lemma 2. For two consistent interpretations ( , ) and ( ′, ′), we have that if ( , ) ⪯ 2 ( ′, ′), then ( , ) ⪯ 2 ( ′, ′).
Proof. Clearly, ( ∖ ( ∖ ′)) ⪯ , thus ′ ⪯ .
Now, we demonstrate how this ordering minimizes truth.
Lemma 3. Given two consistent interpretations ( , ) and ( ′, ′) and an atom s.t. ( , )() ̸=
2
and ( ′, ′)() = , if ( , ) ≺ ( ′, ′) then ( , )() = .
3In Knorr et al.’s Definition 9 [
Proof. By contrapositive, suppose ( , )() = . We have ̸∈ and ∈ . Because ( ′, ′)() = , we have ∈ ′, thus ∈ ( ′ ∖ ). It follows that ̸∈ ′ ∖ ( ′ ∖ ), and then we can conclude ¬( ⪯ ( ′ ∖ ( ′ ∖ ))).
Finally, we show that when minimizing truth, partial consistent interpretations will not be favoured over exact interpretations.
Lemma 4. With ( , ) ⪯ 2 ( ′, ′) s.t. ⊆ , we have = .
Proof. Suppose ⊂ and let ∈ ( ∖ ). We have ( , )() = . From Lemma 2, it follows that ⊆ ′, thus ( ′, ′)() = . We can apply Lemma 3 to conclude ( , )() = , a contradiction.
We now lift ℳ answer sets [
Definition 20. The DI- ℳ semantics are given by using the determining inference structure ⟨ ℳ, ⟨ℒ2, ⪯ 2⟩⟩ with the DI- semantics (Definition 10).
The resulting semantics DI- ℳ is equivalent to ℳ for normal programs [
Example 4. Let be the program given in Example 1. DI- ℳ is faithful to both DI-ℳ (Definition 11) and ℳ semantics (Definition 4). That is, both ({, }, {, }) and ({}, {, }) are DI- ℳ answer sets. No other interpretation is a DI- ℳ answer set. If we add the rule ← , then ({, }, {, , }) and ({}, {, , }) are the DI- ℳ answer sets. The interpretation ({, }, {, , }) is neither a DI-ℳ nor a ℳ answer set.
The example above shows that some non-exact DI- ℳs are not ℳ answer sets. This is by choice as combining ℳ answer sets and DI-ℳ under a single semantics will result in a semantics where not every DI-answer set is ⪯ 2 minimal. The following lemma provides some further insight into the relation between DI- ℳ answer sets and ⪯ 2 .
Lemma 5. If ( , ) is a ℳ answer set of some ′ ∈ ( ) for a DLP , then has a DI- ℳ ( ′, ′) s.t. ( ′, ′) ⪯ 2 ( , ).
This shows that, if desired, one can leverage ⟨ ℳ, ⟨ℒ2, ⪯ 2 ⟩⟩ to obtain a DI- semantics that is ⪯ 2 minimal at the cost of sacrificing some DI- ℳ answer sets (Example 4).
We show that in general, DI- ℳ is faithful to both the original DI-ℳ semantics [
Proposition 2. If ( , ) is a ℳ answer set of , then it is a DI- ℳ answer set of . 2 Proof. By contrapositive, assume ( , ) is not a DI- ℳ of . We have ( ′, ′) ≺ ( , ) s.t. ( ′, ′) is a ℳ answer set of a disjunctive reduct ′ of . It follows that ( ′, ′) ⪯ 2 ( , ) (Lemma 2). With ′ ⊆ and as a model of ′, we have that ( ′, ′) satisfies the reduct of w.r.t. ( , ), thus ( , ) is not a ℳ answer set of .
In general, the converse does not hold, that is, there are some DI- ℳ stable fixpoints that are not ℳ answer sets (see Example 4).
Proposition 3. If ( , ) is a DI-ℳ answer set of , then it is a DI- ℳ answer set of . Proof. For the sake of contradiction, suppose ( , ) is not a DI- ℳ. There exists ( ′, ′) ≺ 2 ( , ) s.t. ( ′, ′) is ℳ answer sets of a disjunctive reduct of the DLP . By Lemma 4, ′ = ′, which contradicts the assumption that ( , ) is a DI-ℳ.
Naturally, it follows that our semantics capture the ℳ answer sets.
Unlike ℳ answer sets, a DI- ℳs is guaranteed to exist.
Proposition 4. Every DLP has a DI-ℳ answer set.
Proof. Let ′ be some disjunctive reduct of the DLP . ′ has a ℳ answer set, then by Lemma 5, has a DI-ℳ.
Using fix to denote the set of fixpoints of a function , we now define a method of filtering stable ifxpoints that is similar to Definition 13 but which minimizes across all stable fixpoints instead of just exact stable fixpoints.
of are contained in the set ⪯ (⋃︀{fix ((ℎ)) | ℎ ∈ }).
We instantiate the above for ℳ answer sets.
Definition 22. Given an approximator set , the DI-ℳ stable fixpoints of are given as the DI- stable fixpoints with ⟨ℳ, ⟨ℒ2, ⪯ 2⟩⟩.
Echoing Theorem 1, but this time for the three-valued case, we show that if a normal answer set semantics has an approximator, the DI- semantics can be characterized using an approximator set. A corresponding approximator set for and a DLP is a set of cardinality |()| s.t. for each ′ ∈ (), there is an approximator in whose stable fixpoints correspond to the -answer sets of ′.4 Theorem 3. Given an answer set semantics , a DLP , and an exact corresponding approximator set , we have that (, ) is a DI- stable fixpoint of (Definition 21) if it is a DI- answer set of (Definition 10).
Proof. Follows proof of Theorem 1.
Given that () is a corresponding approximator set for ℳ, we get the following result from Theorem 3.
Theorem 4. Let (, ) be an interpretation of a DLP . It is a DI-ℳ answer set of if and only if (, ) is a DI-ℳ stable fixpoint of ().
Example 5. Define as the program from Example 1 with the added rule ← . This program has no DI-ℳ answer sets and two DI-ℳ answer sets, namely, the ℳ answer sets ({}, {, , }) and ({, }, {, , }).
Let and be the programs from () that select and respectively from the head of , ← and let ℎ and ℎ be their approximators from ().
We have that ({, }, {, , }) is a stable fixpoint of (ℎ ) and not a fixpoint of (ℎ ) with (ℎ )(({, }, {, , })) = ({}, {, }).
Killen et al. [
for some ℎ ∈ s.t. (, ) ∈ ⪯ 2 {(ℎ)(, ) | ℎ ∈ }.
Comparing DI-stable fixpoint to disjunctive stable fixpoints, we can generalize Proposition 2 to the level of algebra.
2 2 Proposition 5. Given a DI-structure ⟨ , ⟨ℒ ⪯ ⟩⟩, A disjunctive stable fixpoint (Definition 23) of an approximator set is a DI- stable fixpoint of (Definition 21).
That DI-ℳ answer sets subsume ℳ answer sets (Proposition 2) follows from the above. 4Unlike Theorem 1, the corresponding approximator set is not limited to exact pairs Corollary 2. A DI-ℳ stable fixpoint is a disjunctive stable fixpoint (Definition 23).
We can also show that the DI-ℳ stable fixpoints capture the exact DI- ℳ stable fixpoints. Proposition 6. An exact DI-ℳ stable fixpoint (Definition 13) is a DItion 20). ℳ stable fixpoint (Defini
We can discuss the local/global Kripke-Kleene/well-founded fixpoints and states. Now that we have captured DI-ℳ semantics via a set of approximators, we automatically obtain the distinguished ifxpoints and states (Definitions 16, 17, and 18). We briefly instantiate these for a DI- ℳ semantics. Example 6. Define to be the following program There are six programs in (). We denote the program from () that selects the atom from ℎ(, ← ) and from ℎ(, , ← ) as , . Thus, () = {,, ,, ,, ,, ,, ,}. The Kripke-Kleene fixpoints of each program , , i.e., the local KripkeKleene fixpoints of (), take the form ({, }, {, , }). For example, lfp ℎ, = ({, }, {, }). In this case, lfp ℎ, is not a global Kripke-Kleene fixpoint because lfp ℎ, = ({}, {, }) ⪯ 2 ({, }, {, }). The interpretation ({}, {, }) is a global Kripke-Kleene fixpoint and thus it is a part of the Kripke-Kleene state.
We have demonstrated the flexibility of Killen et al.’s [
The connections between DI-ℳ and ℳ rely on the syntactic restriction that ℎ() = ℎ(′) implies ̸= ′ for disjunctive rules. Shen and Eiter use a peculiar method of generating normal programs from a disjunctive logic program. Interestingly, their method of choosing normal programs has little impact on the semantics of disjunctive ℳ answer sets. In general, the method of choosing normal programs greatly impacts the semantics in DI- semantics. In future work, we wish to further generalize determining inference semantics such that this head selection function is parameterized and study this wider family of semantics through the lens of AFT.
Heyninck et al. lift AFT to a nondeterministic setting [
Spencer Killen was partially supported by Alberta Innovates and Alberta Advanced Education.
The authors have not employed any Generative AI tools.