Introduction

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 [1,2,3], assumption-based argumentation [4,5,6,7,8], argumentation frameworks with collective attacks [9], claim-augmented argumentation frameworks [10,11], and abstract dialectical frameworks [12,13].

The multitude of different 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 [14]. Translations from argumentation frameworks into logic programs, on the other hand, allows to utilise the rich toolbox for LPs, e.g., answer set programming solvers like clingo [15], directly on instances of formal argumentation.

Existing translations consider normal LPs [16], i.e., the class of LPs in which the head of each rule amounts precisely to one positive atom. In this work, we take one step further and consider LPs with negation as failure in the head of rule [17]. We investigate the relation of this more general class of LPs to assumption-based argumentation (ABA) [4]. This is a versatile structured argumentation formalism which models argumentative reasoning on the basis of assumptions and inference rules. ABA can be suitably deployed in multi-agent settings to support dialogues [18] and supports applications in, e.g., healthcare [19], law [20] and robotics [21].

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 nonflat ABA [22]) captures the more general fragment of LPs with negation as failure in the head, differently from all of the aforementioned argumentation formalisms. This underlines the increased and more flexible modelling capacities of the generic ABA formalism.

In this work, we investigate the relationship between non-flat ABA and LP with negation in the head, focusing on stable [4] and set-stable [23] semantics. While stable semantics is well understood, the latter has not been studied thoroughly so far. Set-stable semantics has been originally introduced for a restricted non-flat ABA fragment (bipolar ABA [23]) only, with the goal to study the correspondence between ABA and a generalisation of abstract argumentation that allows for support between arguments (bipolar argumentation [24]). In this paper we adopt it for any nonflat ABA framework and study it in the context of LPs with negation as failure in the head.

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 [17].

Background

We recall logic programs with negation as failure in the head [17] and assumption-based argumentation [4].

Logic programs with negation as failure in head

A logic program with negation as failure (naf) in the head [17] (LP in short in the remainder of the paper) consists of a set of rules 𝑟 of the form

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. Negation as failure in the head can be also interpreted in terms of denial integrity constraints, as also observed by Janhunen [25]. Thus, naf literals and constraints are, to some extent, two sides of the same coin. Let us consider the following example.

Example 2.3. Consider the LP 𝑃 given as follows.

𝑃 : 𝑝 ← not 𝑞 𝑞 ← not 𝑝 𝑠 ← not 𝑠 ← 𝑠, not 𝑝.

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:

𝑃 𝐼 1 : 𝑝 ← 𝑠 ← 𝑃 𝐼 2 : 𝑞 ← 𝑠 ← ∅ ← 𝑠

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 𝑠.

Assumption-based Argumentation

We recall assumption-based argumentation (ABA) [4]. A deductive system is a pair (ℒ, ℛ), where ℒ is a formal language, i.e., a set of sentences, and ℛ is a set of inference rules over ℒ. A rule 𝑟 ∈ ℛ has the form 𝑎0 ← 𝑎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) [22] is a tuple (ℒ,ℛ,𝒜, ) for (ℒ,ℛ) a deductive system, 𝒜 ⊆ ℒ the assumptions, and :𝒜 → ℒ a contrary function.

In this work, we focus on finite ABAFs, i.e., ℒ, ℛ, 𝒜 are finite; 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 [23]. 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 [22] and set-stable [23] ABA semantics (abbr. stb and sts, respectively). Note that, while set-stable semantics has been defined for bipolar ABAFs only, we generalise the semantics to arbitrary ABAFs. Definition 2.7. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABAF. Further, let 𝑆 ∈ cf (𝐷) be closed.

Stable Semantics Correspondence

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 (LP-ABA) 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.

From LPs to ABAFs

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 [4]. 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 𝑃 ) iff ∆(𝐼) 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 𝑃 iff 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 differs from reachability based on dependency graphs which is defined for positive atoms only.

Below, we prove our first main result.

By definition of 𝑃𝐼 we obtain 𝐼 is a stable model of 𝑃 iff 𝐼 is a ⊆-minimal model of 𝑃 𝐼 satisfying (𝑎) 𝑝 ∈ 𝐼 iff 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. 1First, 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 iff 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 𝑏𝑜𝑑𝑦 + (𝑟) ⊆ 𝐼 (otherwise, there is an atom 𝑞 / ∈ 𝐼 with a smaller tree-derivation, contradiction to the minimality of 𝑝 in 𝑄). Consequently, we obtain that 𝑝 ∈ 𝐼, contradiction to our initial assumption.

• 𝑆 attacks all other assumptions: Suppose there is an atom 𝑝 ∈ 𝐼 which is not reachable from 𝑆. We show that 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 𝑃 .

𝐼 ′ = 𝐼 ∖ {𝑝} is a model of 𝑃 𝐼 .

• 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 fixed tree-derivation: Let 𝑝 ′ ∈ 𝑏𝑜𝑑𝑦(𝑟). The sub-tree with root 𝑝 ′ is an argument of height 𝑛. Hence, by induction hypothesis, ∆(𝐼) derives 𝑝 ′ , i.e., there is

𝑟 ′ ∈ 𝑃 with ℎ𝑒𝑎𝑑(𝑟 ′ ) = 𝑝 ′ , 𝑏𝑜𝑑𝑦 + (𝑟 ′ ) ⊆ 𝐼,

From ABAFs to LPs

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 LP-ABA fragment. A similar fragment for the case of normal LPs and flat ABAFs has been already considered [6,22,26].

Here, we extend it to the more general case. We show that each LP-ABAF corresponds to an LP, using a translation similar to [6][ Definition 11] (which is however for flat ABA). We replace each assumption 𝑎 with not 𝑎. For an atom 𝑝 ∈ ℒ, we let

rep(𝑝) = {︃ not 𝑝, if 𝑝 ∈ 𝒜 𝑎, if 𝑝 = 𝑎 ∈ 𝒜.

Note that in the LP-ABA fragment, this case distinction is exhaustive. We extend the operator to ABA rules elementwise:

rep(𝑟) = rep(ℎ𝑒𝑎𝑑(𝑟)) ← {rep(𝑝) | 𝑟 ∈ 𝑏𝑜𝑑𝑦(𝑟)}.ℛ : 𝑝 ← 𝑞 𝑞 ← 𝑝 𝑠 ← 𝑠 ← 𝑠, 𝑝.

We replace e.g. the assumption 𝑝 with not 𝑝 and the contrary 𝑝 is left untouched. This yields the associated LP

𝑃𝐷 : 𝑝 ← not 𝑞 𝑞 ← not 𝑝 𝑠 ← not 𝑠 ← 𝑠, not 𝑝.

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. 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. 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 𝑎𝑝. 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 efficiently.

Proposition 3.12. For each ABAF 𝐷 = (ℒ, ℛ, 𝒜, ) there is ABAF 𝐷 ′ computable in polynomial time s.t. (i) 𝐷 ′ is an LP-ABAF and (ii) 𝑆 ∈ stb(𝐷 ′ ) iff 𝑆 ∩ 𝒜 ∈ 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.

Denial Integrity Constraints in ABA

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. 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(𝐷 ′ ). 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.

Set-Stable Model Semantics

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.

Bipolar LPs and Set-Stable Semantics

Recall that an ABAF 𝐷 = (ℒ, ℛ, 𝒜, ) is bipolar iff 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. 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 suffices if the closure of an assumption 𝑎 outside a given set is attacked; that is, it suffices 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. For a bipolar LP 𝑃 and a set 𝑆 ⊆ HB 𝑃 ∪ HB 𝑃 , we define

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 ({𝑎}).

𝑃 : 𝑝 ← not 𝑝 not 𝑞 ← not 𝑝 𝑞 ← not 𝑠.

Then, cl ({not 𝑝}) = {𝑝, not 𝑞, not 𝑝}, cl ({not 𝑞}) = {not 𝑞}, and cl ({not 𝑠}) = {𝑞, not 𝑠}.

We define a modified reduct by adding rules to make the closure explicit: for each atom 𝑎 ∈ HB 𝑃 , if not 𝑏 can be reached from not 𝑎, we add the rule 𝑎 ← 𝑏. 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. 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 .

Definition 4.6. An interpretation 𝐼 ⊆ HB 𝑃 is a set-stable model of an LP 𝑃 if 𝐼 is a ⊆-minimal model of 𝑃 𝐼 𝑠 satisfying (a) 𝑝 ∈ 𝐼 iff there is 𝑟 ∈ 𝑃 𝐼 𝑠 s.t. ℎ𝑒𝑎𝑑(𝑟) = 𝑝 and 𝑏𝑜𝑑𝑦(𝑟) ⊆ 𝐼; (b) there is no rule 𝑟 ∈ 𝑃 𝐼 𝑠 with ℎ𝑒𝑎𝑑(𝑟) = ∅ and 𝑏𝑜𝑑𝑦(𝑟) ⊆ 𝐼.

If we consider the generalised set-stable reduct instead, we find 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 𝑃 .

Set-stable Semantics in general (non-bipolar) LPs

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. We furthermore note that the support of a set of positive and negative atoms can be computed in polynomial time. Lemma 4.9. For a bipolar LP 𝑃 and a set 𝑆 ⊆ HB 𝑃 ∪HB 𝑃 , cl (𝑆) is computable in polynomial time.

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. 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).

Relating ABA and LP under set-stable semantics

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. 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 suffices 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 conflict-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(𝐷) iff Th𝐷(𝑆) ∖ 𝒜 is a setstable model of 𝑃𝐷.

Making use of the translation from general ABA to the LP-ABA fragment outlined in the previous section, we obtain that the correspondence extends to general ABA. 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 {𝑎, 𝑐}.

Set-stable Semantics for General (non-bipolar) ABAFs

The example indicates a fundamental difference 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.

Discussion

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 different 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 [27]), as commonly used ASP solvers (like clingo [15]) can handle constraints. With this, we provide a powerful alternative to solvers for non-flat ABA, which are typically not supported by established ABA solvers due to the primary focus on flat instances (with some exceptions [28,29]). LPs can profit from the thoroughly investigated explanation methods for ABAFs [22,30,31].

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 differences) between the derivation of assumptions and setting constraints.