The relation between (a fragment of) assumption-based argumentation (ABA) and logic programs (LPs) under stable model semantics is well-studied. However, for obtaining this relation, the ABA framework needs to be restricted to being flat, i.e., a fragment where the (defeasible) assumptions can never be entailed, only assumed to be true or false. Here, we remove this restriction and show a correspondence between non-flat ABA and LPs with negation as failure in their head. We then extend this result to so-called setstable ABA semantics, originally defined for the fragment of non-flat ABA called bipolar ABA. We showcase how to define set-stable semantics for LPs with negation as failure in their head and show the correspondence to set-stable ABA semantics.
Computational argumentation and logic programming
constitute fundamental research areas in the field of knowledge
representation and reasoning. The correspondence between
both research areas has been investigated extensively,
revealing that the computational argumentation and logic
programming paradigms are inextricably linked and
provide orthogonal views on non-monotonic reasoning. In
recent years, researchers developed and studied various
translations between logic programs (LPs) and several
argumentation formalisms, including translation from and
to abstract argumentation [
The multitude of diferent translations sheds light on the
close connection of negation as failure and argumentative
conflicts. Apart from the theoretical insights, these
translations are also practically enriching for both paradigms as
they enable the application of methods developed for one
of the formalisms to the other. On the one hand,
translating logic programs to instances of formal argumentation
has been proven useful for explaining logic programs [
Existing translations consider normal LPs [
Research in ABA often focuses on the so-called flat ABA
fragment, which prohibits deriving assumptions from
inference rules. In this work, we show that generic (potentially
non-flat) ABA (referred to improperly but compactly as
nonlfat ABA [
In this work, we investigate the relationship between
non-flat ABA and LP with negation in the head, focusing
on stable [
In more detail, our contributions are as follows:
• We show that each LP with negation as failure in
the head corresponds to a non-flat ABA framework
under stable semantics.
• We identify an ABA fragment (LP-ABA) in which
the correspondence to LPs with negation as failure
in the head is 1-1. We prove that each non-flat ABA
framework corresponds to an LPs with negation as
failure in the head by showing that each ABA
framework can be mapped into an LP-ABA framework.
• We introduce set-stable model semantics for LPs
with negation as failure in the head. We identify the
LP fragment corresponding to bipolar ABA under
set-stable semantics. We furthermore consider the
set-stable semantics for any LPs with negation as
failure in the head by appropriate adaptions of the
reduct underpinning stable models [
We recall logic programs with negation as failure in the
head [
A logic program with negation as failure (naf) in the
head [
0 ← 1, . . . , , not +1, . . . , not not 0 ← 1, . . . , , not +1, . . . , not for ≥ 0, (propositional) atoms , , and naf operator not . We write ℎ() = 0 and ℎ() = not 0, respectively, and () = {1, . . . , , not +1, . . . , not }. Furthermore, we let +() = {1, . . . , } denote the positive and − () = {+1, . . . , } denote the negative atoms occuring in the body of ; moreover, we let ℎ− () = {0} if ℎ() = not 0 and ℎ− () = ∅ otherwise (analogously for ℎ+()).
Definition 2.1. The Herbrand Base of an LP is the set HB of all atoms occurring in . By
HB = {not | ∈ HB } we denote the set of all naf-negated atoms in HB .
We call an LP a normal program if ℎ− () = ∅ for each ∈ and a positive program if − () = ℎ− () = ∅ for each ∈ . Given ⊆ HB , the reduct of is the positive program = {ℎ+() ←
+() | − () ∩ = ∅, ℎ− () ⊆ }.
In contrast to the LP fragment that we consider in this work, the reduct of a program can contain (denial integrity) constraints, i.e., rules with empty head.
We are ready to define stable LP semantics.
Definition 2.2. ⊆ HB is a stable model [
Negation as failure in the head can be also interpreted
in terms of denial integrity constraints, as also observed
by Janhunen [
Example 2.3. Consider the LP given as follows.
Here, models a choice between and . However, as is factual and not entails not (together with the fact ), is rendered impossible.
For the sets of atoms 1 = {, } and 2 = {, } we obtain the following reducts: We see that 1 is a minimal Herbrand model of 1 , whereas 2 is rendered invalid due to the rule ∅ ← . Thus, this rule can be seen as a denial integrity constraint amounting to ruling out the atom .
We recall assumption-based argumentation (ABA) [
1, . . . , for ≥ 0, with ∈ ℒ. We denote the head of by ℎ() = 0 and the (possibly empty) body of with () = {1, . . . , }.
Definition 2.4. An ABA framework (ABAF) [
In this work, we focus on finite ABAFs, i.e., ℒ, ℛ, are ifnite; also, ℒ is a set of atoms or naf-negated atoms.
For a set of assumptions ⊆ , we let = { | ∈ } denote the set of all contraries of assumptions ∈ .
Below, we recall the fragment of bipolar ABAFs [
Next, we recall the crucial notion of tree-derivations. A sentence ∈ ℒ is tree-derivable from assumptions ⊆ and rules ⊆ ℛ , denoted by ⊢ , if there is a finite rooted labeled tree s.t. the root is labeled with ; the set of labels for the leaves of is equal to or ∪ {⊤}, where ⊤ ̸∈ ℒ; for every inner node of there is exactly one rule ∈ such that is labelled with ℎ(), and for each ∈ () the node has a distinct child labelled with ; if () = ∅, has a single child labelled ⊤; for every rule in there is a node in labelled by ℎ(). We often write ⊢ simply as ⊢ . Tree-derivations are the arguments in ABA; we use both notions interchangeably.
Let = (ℒ, ℛ, , ) be an ABAF. For a set of assumptions , by Th() = { ∈ ℒ | ∃′ ⊆ : ′ ⊢ } we denote the set of all sentences derivable from (subsets of) . Note that ⊆ Th() since each ∈ is derivable from {} and rule-set ∅ ({} ⊢∅ ). The closure of is given by cl () = Th() ∩ . An ABAF is flat if each set of assumptions is closed. We refer to an ABAF not restricted to be flat as non-flat .
Definition 2.6. Let = (ℒ, ℛ, , ) be an ABAF. An assumption-set ⊆ attacks an assumption-set ⊆ if ∈ Th() for some ∈ . An assumption-set is conflict-free ( ∈ cf ()) if it does not attack itself; it is closed if () = .
We recall stable [
Definition 2.7. Let = (ℒ, ℛ, , ) be an ABAF. Further, let ∈ cf () be closed. • ∈ stb() if attacks each {} ⊆ ∖ ; • ∈ sts() if attacks cl ({}) for each ∈ ∖ . Example 2.8. We consider an ABAF = (ℒ, ℛ, , ) with assumptions = {, , }, their contraries , , and , respectively, and rules ← .
← .
←
The framework is non-flat because we can derive from .
In , the set {} is set-stable: Clearly, the assumption does not attack itself. It remains to show that the closure of and the closure of is attacked. First note that attacks since {} ⊢ . Thus, attacks also the closure of . It follows that furthermore attacks the closure of since cl ({}) = {, }. This shows that {} is set-stable.
Moreover, the set {, } is stable and set-stable in because it is conflict-free and attacks the assumption via the argument {, } ⊢ .
In this section, we show that non-flat ABA under stable semantics correspond to stable model semantics for logic programs with negation as failure in the head. First, we show that each LP can be translated into a non-flat ABAF; second, we present a translation from a restricted class of ABAFs (LPABA) into LPs; third, we extend the correspondence result to general ABAFs by providing a translation from general non-flat ABA into LP-ABA. We conclude this section by discussing denial integrity constraints in non-flat ABA.
Each LP can be interpreted as ABAF with assumptions
not and contraries thereof, for each literal in the Herbrand
base HB of . We recall the translation from normal
programs to flat ABA [
Definition 3.1. The ABAF corresponding to an LP is = (ℒ, ℛ, , ) with ℒ = HB ∪ HB , ℛ = , = HB , and not = for each not ∈ . Example 3.2. Consider again the LP from Example 2.3. and contrary function not = for each ∈ {, , }. Recall that 1 = {, } is a stable model of . Naturally, this set corresponds to the singleton assumption-set = {not }. Indeed, since is derivable from {not } and is factual, it holds that Th () = {not , , } which sufices to see that ∈ stb( ).
Let us generalize the observations we made in this example. We translate a set of atoms (in HB for an LP ) into an assumption-set ∆( ) (in the ABAF ) by collecting all assumptions “not ” corresponding to the atoms outside ; that is, we set ∆( ) = {not | ∈/ }.
We will prove that is a stable model (in ) if ∆( ) is a stable extension (in ). First, we introduce a notion of reachability in logic programs that is based on the construction of arguments.
Definition 3.3. Let be an LP. An atom ∈ HB ∪ HB is reachable from a set of naf literals ⊆ HB if there is a tree-based argument ′ ⊢ with ′ ⊆ in the corresponding ABAF .
Note that the reachability target is defined for both positive and negative atoms; the source on the other hand is always a set of naf literals. The notion difers from reachability based on dependency graphs which is defined for positive atoms only.
Below, we prove our first main result.
Theorem 3.4. Let be an LP and the ABAF corresponding to . Then is a stable model of if ∆( ) ∈ stb( ). Proof. By definition, a set is stable if it is ⊆ -minimal model of satisfying () ∈ if there is ∈ such that ℎ() = and () ⊆ ; and () there is no ∈ with ℎ() = ∅ and +() ⊆ .
By definition of we obtain is a stable model of if is a ⊆ -minimal model of satisfying () ∈ if there is ∈ such that ℎ() = , +() ⊆ , and − () ∩ = ∅; and () there is no ∈ with ℎ+() = ∅, ℎ− () ⊆ , +() ⊆ , and − () ∩ = ∅.
Below, we show that the first item and the ⊆ -minimality requirement captures conflict-freeness (no naf literal in is derived) and the requirement that all other assumptions are attacked (all other naf literals outside are derived); whereas the second item ensures closure of the program.1
First, Let be a stable model of and let = ∆( ). We show that is stable in , i.e., it is conflict-free, closed, and attacks all assumptions in ∖ .
• is conflict-free: is conflict-free if there is no ∈ HB ∖ such that is reachable, i.e., can be derived from . If such a derivation would exist, then the assumption not ∈ were attacked by . Towards a contradiction, suppose there is an atom ∈ HB ∖ which is reachable from . Let
= { ∈ HB ∖ | ⊢ } denote the set of atoms that are reachable from but lie ‘outside’ . We order according the height of the smallest tree-derivation.
Wlog, we can assume that our chosen atom is
minimal in , i.e., there is no other atom ∈ HB ∖
which is reachable in less steps. Let ′ ⊢ denote
the smallest tree-derivation, and let denote the
top-rule (the rule connecting the root with the fist
level of the tree) of the derivation. The rule satisfies
ℎ() = , − ()∩ = ∅, and +() ⊆
1We note that in the case of normal logic programs without negation
in the head, the second condition does not apply. It is well known and
has been discussed thoroughly in the literature that (a) holds if Δ()
is stable in [
This concludes the proof of the first direction. We have shown that = (∆ ) is stable in .
Now, let = ∆( ) be a stable extension in . We show that is stable in .
• Let ∈ . Then we can construct an argument ′ ⊢ , ′ ⊆ in , i.e., is reachable from . We show that there is a rule with +() ⊆ , − () ∩ = ∅ and ℎ() = . We proceed by induction over the height of the argument, that is, the height of the tree-derivation.
– Base case: Suppose ′ ⊢ has height 1.
Then there is ∈ with ℎ() = , +() = ∅, and − () ∩ = ∅. – ↦→ + 1: Suppose now that the statement holds for all arguments of height smaller than or equal to , and suppose ′ ⊢ has height + 1. Let denote the top-rule of the treederivation.
We derive the statement by applying the induction hypothesis to all height-maximal subarguments (with claims in ()) of our ifxed tree-derivation: Let ′ ∈ (). The sub-tree with root ′ is an argument of height . Hence, by induction hypothesis, ∆( ) derives ′, i.e., there is ′ ∈ with ℎ(′) = ′, +(′) ⊆ , and − (′) ∩ = ∅.
In case ′ is a positive literal, we obtain ′ ∈ (by (a) from Definition 2.2); in case ′ is a naf literal, we obtain ′ ∈ ∆( ) (by (b)). Since ′ was arbitrary, we obtain +() ⊆ and − () ∩ = ∅. • For the other direction, suppose there is a rule ∈ with +() ⊆ , − () ∩ = ∅ and ℎ() = . We can construct arguments for all +() ⊆ and thus obtain ∈ . • Towards a contradiction, suppose there is a ∈ with +() ⊆ , − () ∩ = ∅ and ℎ() = not for some ∈ . Then we can construct an argument for not , contradiction to being closed. • It remains to show that is a ⊆ -minimal model of . Since each atom ∈ has an argument in we obtain minimality: Towards a contradiction, suppose there is a model ′ ⊊ of . Let ∈ ∖ ′. Since there is an argument deriving there is some ∈ with ℎ() = and () ⊆ , showing that ′ is not a model of .
For the other direction, we define a mapping so that each assumption corresponds to a naf-negated atom. However, we need to take into account that ABA is a more general formalism. Indeed, in LPs, there is a natural bijection between ordinary atoms and naf-negated ones (i.e., corresponds to not ). Instead, in ABAFs, assumptions can have the same contrary, they can be the contraries of each other, and not every sentence is the contrary of an assumption in general. To show the correspondence (under stable semantics), we proceed in two steps: 1. We define the LP-ABA fragment in which i) no assumption is a contrary, ii) each assumption has a unique contrary, and iii) no further sentences exist, i.e., each element in ℒ is either an assumption or the contrary of an assumption. We show that the translation from such LP-ABAFs to LPs is semanticspreserving. 2. We show that each ABAF (whose underpinning language is restricted to atoms and their naf) can be transformed to an LP-ABAF whilst preserving semantics.
Relating LP and LP-ABA Let us start by defining the
LPABA fragment. A similar fragment for the case of normal
LPs and flat ABAFs has been already considered [
Definition 3.5. The LP-ABA fragment is the class of all ABAFs = (ℒ, ℛ, , ) where (1) ∩ = ∅, (2) the contrary function is injective, and (3) ℒ = ∪ .
We show that each LP-ABAF corresponds to an LP, using
a translation similar to [
Note that in the LP-ABA fragment, this case distinction is exhaustive. We extend the operator to ABA rules elementwise: rep() = rep(ℎ()) ← { rep() | ∈ ()}. Definition 3.6. For an LP-ABAF = (ℒ, ℛ, , ), we deifne the associated LP = {rep() | ∈ ℛ}.
Example 3.7. Let be an ABAF with = {, , } and ℛ : ← ← ← ← , .
We replace e.g. the assumption with not and the contrary is left untouched. This yields the associated LP : ←
Striving to anticipate the relation between and , note that = {} ∈ stb(). Now we compute Th() ∖ = {, } noting that it is a stable model of .
It can be shown that, when restricting to LP-ABA, the translations in Definitions 3.1 and 3.6 are each other’s inverse. Below, we let
rep() = (rep(ℒ), rep(ℛ), rep(), ) where rep() = .
Lemma 3.8. For any LP , it holds that = . Proof. Each naf atom not corresponds to an assumption in whose contrary is . Applying the translation from Definition 3.6, we map each assumption not to the naf literal not not = not . Hence, we reconstruct the original LP .
We obtain a similar result for the other direction, under the assumption that each literal is the contrary of an assumption, i.e., if ℒ = ∪ as it is the case for the LP-ABA fragment. The translations from Definition 3.6 and 3.1 are each other’s inverse modulo the simple assumption renaming operator rep as defined above. Note that we associate each assumption ∈ with not .
Lemma 3.9. Let = (ℒ, ℛ, , ) be an ABAF in the LP fragment. It holds that = rep().
Proof. When applying the translation from ABA to LP ABA, we associate each assumption ∈ with a naf literal not . Applying the translation from Definition 3.1, each naf literal not is an assumption in . We obtain = (rep(ℒ), rep(ℛ), rep(), ) where rep() = .
We are ready to prove the main result of this section. We make use of Theorem 3.4 and obtain the following result. Theorem 3.10. Let = (ℒ, ℛ, , ) be an LP-ABAF and let be the associated LP . Then, ∈ stb() if Th() ∖ is a stable model of .
Proof. It holds that is stable in if
rep() = {not | ∈ } is stable in rep(). This in turn is equivalent to rep() is stable in (by Proposition 3.9). Equivalently, { | not ∈/ rep()} = { | ∈/ } = Th() ∖ is stable in (by Proposition 3.4). This in turn holds if Th() ∖ is stable in (by definition, = {rep() | ∈ ℛ} = ).
From ABA to LP-ABA To complete the correspondence result between ABA and LP, it remains to show that each ABAF can be mapped to an LP-ABAF ′. To do so, we proceed as follows: 1. For each assumption ∈ we introduce a fresh atom ; in the novel ABAF ′, is the contrary of . 2. If is the contrary of in the original ABAF , then we add a rule ← to ′. 3. For any atom that is neither an assumption nor a contrary in , we add a fresh assumption and let be the contrary of .
Example 3.11. Consider the ABAF with literals ℒ = {, , , , }, assumptions = {, , }, and their contraries = , = , and = , respectively, with rules ℛ : 1 = ← , 2 = ← , 3 = ← .
First note that {} ∈ stb(). We construct the LP-ABAF ′ by adding rules ← , ← , and ← ; , , and are the novel contraries. Moreover, is neither a contrary nor an assumption, so we add a novel assumption with contrary . The stable extension {} is only preserved under projection: we now have {, } ∈ stb(′).
We show that each ABAF can be mapped into an (under projection) equivalent LP-ABAF ′. We furthermore note that the translation can be computed eficiently.
Proposition 3.12. For each ABAF = (ℒ, ℛ, , ) there is ABAF ′ computable in polynomial time s.t. (i) ′ is an LP-ABAF and (ii) ∈ stb(′) if ∩ ∈ stb(). Proof. Let = (ℒ, ℛ, , ) be an ABAF and let ′ = (ℒ′, ℛ′, , ′) be ABAF constructed as described, i.e., 1. For each assumption ∈ we introduce a fresh atom ; in the novel ABAF ′, is the contrary of . 2. If is the contrary of in the original ABAF , then we add a rule ← . 3. For any atom that is neither an assumption nor a contrary in , we add a fresh assumption and let be the contrary of in ′.
First of all, the construction is polynomial. Towards the semantics, let us denote the result of applying steps (1) and (2) by * . We show that in and * the attack relation between semantics persists.
Let ⊆ be a set of assumptions. In the following, we make implicit use of the fact that entailment in and * coincide except the additional rules deriving certain contraries in * .
(⇒) Suppose attacks in for some ∈ . Then ∈ Th() where = . By construction, ∈ Th* () as well and since = , the additional rule ← is applicable. Consequently, ∈ Th* (), i.e., attacks in * as well.
(⇐) Now suppose attacks in * for some ∈ . Then ∈ Th* () which is only possible whenever ∈ Th* () holds for the original contrary of . Thus attacks in .
We deduce
stb() = stb(* ).
Finally, for moving from * to ′ we note that adding assumptions (which do not occur in any rule) corresponds to adding arguments without outgoing attacks to the constructed AF * . This has (under projection) no influence on the stable extensions of * . Consequently ∈ stb(′) ⇔ ∩ ∈ stb(* ) ⇔ ∩ ∈ stb(). as desired.
Given an ABAF , we combine the previous translation with Definition 3.6 to obtain the associated LP . Thus, each ABAF can be translated into an LP, as desired. Example 3.13. Let us consider again the ABAF from Example 3.11. As outlined before, applying the translation into an LP-ABA ′ yields an ABAF ′ with assumptions = {, , , , } their contraries = , = , = , = , and = , respectively, and with rules ← ←
The set {, , } is the stable model corresponding to our stable extension {} from (under projection).
Our correspondence results allow for a novel interpretation of the derivation of assumptions in ABA in the context of stable semantics. Analogous to the correspondence of naf in the head and allowing for constraints (rules with empty head) in LP we can view the derivation of an assumption as setting constraints: for a set of assumptions ⊆ and an assumption ∈ , a derivation ⊢ intuitively captures the constraint ← , , i.e., one of ∪ {} is false.
Thus, our results indicate that deriving assumptions is the same as imposing constraints. More formally, the following observation can be made.
Proposition 3.14. Let = (ℒ, ℛ, , ) be an ABAF and let ′ = (ℒ, ℛ ∪ {}, , ) for a rule of the form ← with ∪ {} ⊆ . Then, ∈ stb(′) if (i) ∈ stb() and (ii) ̸⊆ or ∈ .
Proof. We first make the following observation. We have : Th() ⊆
Th′ () ∀ ⊆ by definition and
∈ Th′ () ∖ Th() ⇒ ∈/ because the only additional way to make deriviations in ′ is through a rule entailing . This, however, implies closed in ′ ⇒ Th() = Th′ (), (1) i.e., for sets closed in ′, the derived atoms coincide.
Now let us show the equivalence.
(⇒) Suppose ∈ stb(′). Since is closed, ̸⊆ or ∈/ , so condition (ii) is met. Moreover, by (1), is conflict-free and attacks each ∈/ in , i.e., ∈ stb(). Thus condition (i) is also met.
(⇐) Let ∈ stb() and let ̸⊆ or ∈ . Then is also closed in ′. We apply (1) and find ∈ stb(′). Example 3.15. Consider the ABAF with assumptions = {, , , }, and their contraries , , , and , respectively, with rules 1 = ←
Intuitively, this rule encodes the constraint ← , , i.e., and cannot be true both at the same time. Consequently, the ABAF ′ has a single stable model 1.
In this section, we investigate set-stable semantics in the context of logic programs.
Set-stable semantics has been originally introduced for bipolar ABAFs (where each rule is of the form ← with an assumption and either an assumption or the contrary thereof) for capturing existing notions of stable extensions for bipolar (abstract) argumentation; we will thus first identify the corresponding LP fragment of bipolar LPs and introduce the novel semantics therefor. We then show that this semantics corresponds to set-stable ABA semantics, even in the general case. Interestingly, despite being the formally correct counter-part to set-stable ABA semantics, the novel LP semantics exhibits non-intuitive behavior in the general case, as we will discuss.
Recall that an ABAF = (ℒ, ℛ, , ) is bipolar if each rule is of the form ← where is an assumption and is either an assumption or the contrary of an assumption. We adapt this to LPs as follows.
Definition 4.1. The bipolar LP fragment is the class of LPs with |()| = 1 and () ⊆ HB for all ∈ .
We note that the head of a rule corresponds by definition either to an assumption (if it is a naf literal) or the contrary of an assumption (if it is a positive literal).
We set out to define our new semantics. In ABA, setstable semantics relaxes stable semantics: it sufices if the closure of an assumption outside a given set is attacked; that is, it sufices if “supports” an attacked assumption , e.g., if the ABAF contains the rule ← . Let us discuss this for bipolar LPs: given a set of atoms ⊆ HB in a program , we can accept an atom not only if it is reachable from ∆( ), but also if there is some reachable and not “supports” not . For instance, given the rule of the form not ← not ∈ , we are allowed to add the contraposition ← to the program before evaluating our potential model .
To capture all “supports” between naf-negated atoms, we define their closure, amounting to the set of all positive and naf-negated atoms obtainable by forward chaining. Definition 4.2.
HB , we define
HB ∪ supp() = ∪ { | ∃ ∈ : () ⊆ , ℎ() = }. The closure of is defined as cl () = ⋃︀>0 supp().2
Note that cl () returns positive as well as negative atoms. For a singleton {}, we write cl () instead of cl ({}). Example 4.3. Consider the bipolar LP given as follows. 2supp() denotes the -th application of supp(· ) to .
Definition 4.4. For a bipolar LP and ⊆ HB , the setstable reduct of is defined as = ∪ where = { ←
| , ∈ HB , ̸= , not ∈ cl ({not })}.
Note that we require ̸= to avoid constructing redundant rules of the form “ ← ”.
Example 4.5. Let us consider again the LP from Example 4.3. Let 1 = {} and 2 = {, }. We compute the set-stable reducts according to Definition 4.4. First, we compute the reducts 1 and 2 . Second, for each naf literal not , we add a rule ← , for each ∈ HB with not ∈ cl ({not }), to both reducts. Inspecting the computed closures of the naf literals of , this amounts to adding the rule ( ← ) to each reduct.
Overall, we obtain 1 : ← 2 : ∅ ← ← ← ← ←
We are ready to give the definition of set-stable semantics. Note that we state the definition for arbitrary (not only bipolar) LPs.
Definition 4.6. An interpretation ⊆ HB is a set-stable model of an LP if is a ⊆ -minimal model of satisfying (a) ∈ if there is ∈ s.t. ℎ() = and () ⊆ ; (b) there is no rule ∈ with ℎ() = ∅ and () ⊆ .
Example 4.7. Consider again the LP from Example 4.3. It can be checked that has no stable model. Indeed, the reduct 1 contains the unsatisfiable rule (∅ ← ); the set 2 = {, } on the other hand is not minimal for 2 .
If we consider the generalised set-stable reduct instead, we ifnd that the set 2 is a ⊆ -minimal model for 2 . The atom is factual in 2 and the atom is derived by . Thus, 2 is set-stable in .
So far, we considered set-stable model semantics in the bipolar LP fragment. As it is the case for the set-stable ABA semantics, our definition of set-stable LP semantics generalises to arbitrary LPs, beyond the bipolar class.
Set-stable model semantics belong to the class of twovalued semantics, that is, each atom is either set to true or false (no undefined atoms exist). Moreover, set-stable model semantics generalises stable model semantics: each stable model of an LP is set-stable, but not vice versa, as Example 4.7 shows.
Proposition 4.8. Let be an LP. Each stable model of is set-stable (but not vice versa).
Proof. Let denote a stable model of . By definition, the generalised reduct of is a superset of all rules in . Thus (a) and (b) in Definition 4.6 are satisfied. Moreover, is ⊆ -minimal by Definition 2.2.
We furthermore note that the support of a set of positive and negative atoms can be computed in polynomial time.
cl () is computable in polynomial time.
HB ∪HB ,
It follows that the computation of a set-stable model of a given program is of the same complexity as finding a stable model.
In the case of general LPs, however, the novel semantics exhibits counter-intuitive behavior, as the following example demonstrates.
Example 4.10. Consider the following two LPs 1 and 2: 1 : ← 2 : ←
In 1 the set {, } is set-stable because we can take the contraposition of the rule and obtain ← . This is, however, not possible in 2 which in fact has no set-stable model.
The example indicates that the semantics does not generalise well to arbitrary LPs. We note that a possible and arguably intuitive generalisation of set-stable model semantics would be to allow for contraposition for all rules that derive a naf literal. This, however, requires disjunction in the head of rules. Applying this idea to Example 4.10 yields the rule ∨ ← when constructing the reduct with respect to 2. The resulting instance therefore lies in the class of disjunctive LPs (a thorough investigation of this proposal however is beyond the scope of the present paper).
In the previous subsection, we identified certain shortcomings of set-stable semantics when applied to general LPs. This poses the question whether our formulation of setstable LP semantics is indeed the LP-counterpart of setstable ABA semantics. In this subsection, we show that, despite the unwanted behavior of set-stable model semantics for LPs, the choice of our definitions is correct: set-stable ABA and LP semantics correspond to each other. We show that our novel LP semantics indeed captures the spirit of ABA set-stable semantics, even in the general case.
We show that the semantics correspondence is preserved under the translation presented in Definition 3.1. We prove the following theorem.
Theorem 4.11. For an LP and its associated ABAF , is set-stable in if ∆( ) is set-stable in .
Proof. By definition, is set-stable if it is a ⊆ -minimal model of satisfying (a) ∈ if there is ∈ s.t. ℎ() = and () ⊆ ; (b) there is no ∈ with ℎ() = ∅ and () ⊆ .
Equivalently, by definition of , () ∈ if (1) there is ∈ s.t. ℎ() = , +() ⊆
and − () = ∅; or (2) there is ∈ such that not ∈ cl (not ) and there is ∈ s.t. ℎ() = , +() ⊆ and − () = ∅; and (b) there is no ∈ with ℎ+() = ∅, ℎ− () ⊆ , ⊆ +(), and − () = ∅.
The second item (b) is analogous to the proof of Theorem 3.4; item (a1) corresponds to item (a) of the proof of Theorem 3.4. Item (a2) formalises that it sufices to (in terms of ABA) attack the closure of a set.
Let be a set-stable model of . We show that = ∆( ) is set-stable in , i.e., is coniflct-free, closed, and attacks the closure of all remaining assumptions. The first two points are analogous to the proof of Theorem 3.4. Below we prove the last item.
• attacks the closure of all other assumptions: Suppose there is an atom ∈ which is not reachable from and there is no ∈ with not ∈ cl (not ). Similar to the proof in Theorem 3.4, we can show that ′ = ∖ {} is a model of . By assumption there is is no rule ∈ such that ℎ() = , +() ⊆ ′, and − () ∩ ′ = ∅ (otherwise, is reachable from ); moreover, there is no rule ← in (otherwise, not is in the support from not ). We obtain that ′ is a model of , contradiction to our initial assumption.
Next, we prove the other direction. Let = ∆( ) be a set-stable extension of . We show that is set-stable in . Similar to the proof of Theorem 3.4 we can show that all constraints are satisfied and that is indeed minimal. Also, the remaining correspondence proceeds similar as in the case of stable semantics, as shown below.
• Let ∈ . Then either we can construct an argument ′ ⊢ , ′ ⊆ in , or there is some ∈ such that not ∈ cl (not ) for which we can construct an argument in . If the former holds, then we proceed analogously to the corresponding part in the proof of Theorem 3.4 and item (a1) is satisfied. Now, suppose the latter is true. Analogously to the the proof of Theorem 3.4, we can show that there is a rule ∈ with +() ⊆ , − () ∩ = ∅ and ℎ() = , that is (a2) is satisfied. • For the other direction, suppose there is a rule ∈ with +() ⊆ , − () ∩ = ∅ and ℎ() = and there is ∈ with not ∈ cl (not ) and ℎ() = , +() ⊆ and − () = ∅ for some . We can construct arguments for all +() ⊆ and thus ∈ .
Analogous to the case of stable semantics, we can show that the LP-ABA fragment preserves the set-stable semantics and obtain the following result.
Theorem 4.12. Let be an LP-ABAF and let be the associated LP. Then, ∈ sts() if Th() ∖ is a setstable model of .
Making use of the translation from general ABA to the LPABA fragment outlined in the previous section, we obtain that the correspondence extends to general ABA.
Recall that Example 4.10 indicates that the semantics does not generalise well in the context of LPs. In light of the close relation between ABA and LP, it might be the case that the non-intuitive behavior afects set-stable ABA semantics. However, we find that set-stable semantics generalise well for ABAFs. The reason lies in the diferences between deriving assumptions (in ABA) and naf literals (in LPs) beyond classical stable model semantics.
Let us translate Example 4.10 in the language of ABA. Example 4.13. The translation of the LPs 1 and 2 from Example 4.10 yields two ABAFs 1 and 2. The ABAF 1 has two assumptions 1 = {, } (representing not and not , respectively) with contraries and , and rules ℛ1 : ← .
← .
The ABAF 2 has three assumptions 2 = {, , } (representing not , not , and not , respectively) with contraries , , , and rules ℛ2 : ← .
← , .
By Theorem 4.11, we obtain the set-stable extensions of the ABAFs from our results from the original programs 1 and 2. In 1, the empty set is set-stable because it attacks the closure of each assumption. In 2, on the other hand, no set of assumptions is set-stable: and are not attacked, although they jointly derive which is attacked by the empty set.
In contrast to the LP formulation of the problem where taking the contraposition of each rule with a naf literal in the head would have been a more natural solution, the application of set-stable semantics in the reformulation of Example 4.10 confirms our intuition. The set {, } derives the assumption , however, the attack onto is not propagated to (the closure of) one of the members of {, }.
The example indicates a fundamental diference between deriving assumptions and naf literals in ABA and LPs, respectively. A rule in an LP with a naf literal in the head is interpreted as denial integrity constraint (under stable model semantics). As a consequence, the naf literal in the head of a rule is replaceable with any positive atom in the body; e.g., the rules not ← , and not ← , are equivalent as they both formalise the constraint ← , , . Although a similar behavior of rules with assumptions in the head can be identified in the context of stable semantics in ABA, the derivation of an assumption goes beyond that; it indicates a hierarchical dependency between assumptions.
In this work, we investigated the close relation between non-flat ABA and LPs with negation as failure in the head, focusing on stable and set-stable semantics. Research often focuses on the flat ABA fragment in which each set of assumptions is closed. This restriction has however certain limitations; as the present work demonstrates, non-flat ABA is capable of capturing a more general LP fragment, thus opening up more broader application opportunities. To the best of our knowledge, our work provides the first correspondence result between an argumentation formalism and a fragment of logic programs which is strictly larger than the class of normal LPs. We furthermore studied set-stable semantics, originally defined only for bipolar ABAFs, in context of general non-flat ABAFs and LPs.
The provided translations have practical as well as
theoretical benefits. Conceptually, switching views between
deriving assumptions (as possible in non-flat ABA) and
imposing denial integrity constraints (as possible in many
standardly considered LP fragments) allows us to look at a
problem from diferent angles; oftentimes, it can be
helpful to change viewpoints for finding solutions. Practically,
our translations yield mutual benefits for both fields. Our
translations from ABA into LP yield a solver for non-flat
ABA instances (as, for instance, employed in [
The generalisation of set-stable model semantics to the non-bipolar ABA and LP fragment furthermore indicated interesting avenues for future research. As Example 4.10 indicates, the semantics does not generalise well beyond the bipolar LP fragment. It would be interesting to further investigate reasonable generalisations for set-stable model semantics for LPs. As discussed previously, a promising generalisation might lead us into the fragment of disjunctive LPs. Another promising direction for future work would be to further study and develop denial integrity constraints in the context of ABA, beyond stable semantics. A further interesting avenue for future work is the development and investigation of three-valued semantics (such as partialstable or L-stable model semantics) for LPs with negation as failure in the head, in particular in correspondence to their anticipated ABA counter-parts (e.g., complete and semistable semantics, respectively).
As the case of set-stable semantics indicates, it is unlikely that the correspondence between denial integrity constraints and assumptions in the head is satisfied beyond stable semantics. It would be interesting to investigate denial integrity constraints in the realm of ABA, to shed light on the relation (and diferences) between the derivation of assumptions and setting constraints.
This research was funded in whole, or in part, by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 101020934, ADIX) and by J.P. Morgan and by the Royal Academy of Engineering under the Research Chairs and Senior Research Fellowships scheme; by the Federal Ministry of Education and Research of Germany and by Sächsische Staatsministerium für Wissenschaft, Kultur und Tourismus in the programme Center of Excellence for AI-research “Center for Scalable Data Analytics and Artiifcial Intelligence Dresden/Leipzig”, project identification number: ScaDS.AI.