Semantics for Non-Flat Assumption-Based Argumentation, Revisited

1 Introduction andMotivation

Argumentation theory is a well-established AI-based discipline for reasoning with arguments and counterarguments [Dung, 1995; Baroni et al., 2018; Gabbay et al., 2021]. Assumption-based argumentation frameworks (ABFs, for short) [Bondarenko et al., 1997] are argumentative formalisms in which reasoning is based on knowledge-bases consisting of strict premises, inference rules, and (defeasible) assumption. These frameworks have been extensively studied and applied in the last twenty years (see [Dung et al., 2009; Toni, 2014; ˇCyras et al., 2018] for some relevant tutorials).

A primary goal of argumentation theory is to identify sets of arguments or assumptions that can be reasonably upheld together, since they are not conflicting and defend themselves from any argumentative attacks. This can be done using semantics in terms of three-valued labeling functions [Schulz and Toni, 2017; Baroni et al., 2021], assigning to each assumption the value in (intuitively, accepted), out (intuitively, rejected) or undec (intuitively, undecided). In ABFs, it is also possible to express relations between assumptions using rules. Such ABFs are called non-flat, as opposed to flat ABFs where rules with assumptions in their conclusion are not allowed. It is reasonable to require, in addition to properties such as defense and conflict-freeness, that reasonable labellings are closed under the strict rules: any assumption that can be derived from an accepted set of formulas should also be accepted. In that case, however, not every ABF might admit a reasonable argumentation labelling:

Example 1. Consider the assumptions p, q and r. Suppose that p implies r, while q refutes r (see Figure 1).

Then, on one hand, the elements of S = {p, q} can be collectively accepted (since S is not contradictory) and also stand on their own (as no assertion challenges the elements in S). On the other hands, S is not deductively closed, as it implies an assertion (r) which is not its element (and cannot be added to S without violating its inconsistency). Moreover, while S itself is consistent, its set of conclusions is not consistent. In more technical parlance (see Definition 3), we say that this ABF does not admit a complete extension.

The non-existence of complete extensions in Example 1 isn't the only problem of non-flat ABFs. Indeed, several desired properties that hold for other argumentative formalisms are violated by non-flat ABFs. In the terminology of Definition 3, this includes the uniqueness of the grounded extension and the completeness of preferred extensions [ ˇCyras et al., 2018]. Moreover, reasoning tasks with non-flat ABFs are often of higher computational complexity [ ˇCyras et al., 2021].

The situation in Example 1 suggests that 3-valued semantics to non-flat ABFs is not sufficiently fine-grained. In particular, we argue that both p and q should be accepted in the last case, while r should be assigned a value indicating that it is contradictory, and so a controversial conclusion. This requires a refinement of 3-valued labeling semantics that properly distinguishes between different cases of uncertainty (e.g., incompleteness versus inconsistency). Remaining on the intuitive level, we aim for a proper semantics, meeting the following desirable properties:

• D1 Generalization of the semantics of flat ABFs.
• D2 Extension of standard semantics for non-flat ABFs (when they exist).
• D3 Keeping common properties of standard argumentation semantics: uniqueness of the grounded extension, com-

pleteness of the preferred extension and preservation of the complexity of flat ABFs.

We notice that there are already a number extensions of 3-valued labeling semantics for argumentative frameworks, such as the 4-valued lablings in [Jakobovits and Vermeir, 1999; Arieli, 2016; Bistarelli and Taticchi, 2021] (see also the survey in [Arieli, 2022]), however they provide semantics to abstract argumentation frameworks (AAFs) rather than to ABFs, thus disregard the logical relations among arguments, and so cannot satisfy D1-D3.

Outline of the Paper: In Section 2 we recall the necessary material on ABFs. In Section 3 we define the underline algebraic structures, and in Section 4 we consider the refined semantics, using operators on these structures. In Section 5 we prove that our formalism meets the desiderata listed above, and in Section 6 we refer to some related work and conclude.

2 Preliminaries on ABFs

We first describe what assumption-based argumentation frameworks (ABFs) are. The definitions and notations in this section are based on [Bondarenko et al., 1997], where ABFs are described as formal models that allow to use plausible assumptions to extend a given theory, unless and until there are good reasons for not using some of the assumptions.

Our starting point is a deductive system (L,R), consisting of a language L (namely, a countable set of formulas) and a set R or inference rules of the form

where ψ1, . . . , ψn ∈ L are the rule's conditions (or the rule's body), and ψ ∈ L is the rule's conclusion (or the rule's head).

An R-deduction from a theory T ⊆ L is a sequence of formulas ϕ1, . . . , ϕm (m ≥ 1), such that for all 1≤i≤m either ϕi ∈ T or there is a rule in Rwhose conclusion is ϕi and whose conditions are in {ϕ1, . . . , ϕi-1}. We denote T ⊢R ψ, if there is an R-deduction from T whose last element is ψ.

Definition 1. An assumption-based framework (ABF) is a tuple ABF = 〈(L, R), Γ, ∆, ∼〉, where:

• (L,R) is a deductive system,
• Γ ⊆ L is a set of the strict assumptions,
• ∆ ⊆ L is a nonempty set of the defeasible assumptions,
• ∼ : ∆ → L is a contrariness operator.

The set Γ is assumed to be R-consistent, namely: there is no ψ ∈ ∆ such that Γ ⊢R ψ and Γ ⊢R ∼ψ. In what follows, we also assume that ∆ is a countable set. Generalization of the results to uncountable sets is easy.

Example 2. The setting from Example 1 may be represented by an ABF in which Γ = ∅, ∆ = {p, q, r}, R = { pr , q ¬r }, and ∼ψ = ¬ψ for every ψ ∈ ∆. 1

Conflicts (attacks) between sets of defeasible assumptions are defined as follows:

1 In all the examples that follow, we implicitly assume that the contrariness operator ∼ is expressed by the negation connective ¬.

Definition 2. Let ABF = 〈(L,R), Γ,∆,∼〉 be an ABF, ψ ∈ ∆, and Θ, Θ′ ⊆ ∆. We say that Θ attacks ψ if Γ, Θ ⊢R ∼ψ, and Θ attacks Θ′ if Γ, Θ ⊢R ∼ψ for some ψ ∈ Θ′ . Now,

• Θ is closed, iff Θ = {ψ ∈ ∆ | Γ, Θ ⊢R ψ}.
• Θ+ = {Λ ⊆ ∆ | Θ attacks Λ}.
• Θ- = {Λ ⊆ ∆ | Λ is closed and attacks Θ}.

Note 1. In most structured accounts of argumentation-based formalisms, attacks are defined between arguments, which are deductions in a given deductive or defeasible system (e.g., ASPIC+ [Modgil and Prakken, 2014], defeasible logic programming [Garc´ıa and Simari, 2004]) or sequents of the form Γ,Θ ⊢L ψ where L is an underlying core logic ([Besnard and Hunter, 2001; Arieli and Straßer, 2015]). 2 In contrast, assumption-based argumentation can be seen as operating at a higher level of abstraction, since attacks are defined directly on sets of assumptions instead of on R-deductions. In this context, arguments in ABF = 〈(L,R), Γ,∆,∼〉 may be viewed as pairs 〈∆′ , ψ〉 where Γ,∆′ ⊢R ψ for some ∆′ ⊆ ∆. 3 ABFs can thus be viewed as operating on equivalence classes consisting of arguments with the same premises.

Consequences of a given assumption-based framework are determined with the use of argumentation semantics, which determines sets of assumptions that are acceptable given different criteria of acceptability. Argumentation semantics have been phrased for abstract frameworks in [Dung, 1995] and were adjusted to assumption-based frameworks in e.g. [Bondarenko et al., 1997].

Definition 3. Let ABF = 〈(L,R), Γ,∆,∼〉 be an ABF, and let Θ ⊆ ∆. We say that Θ

• is conflict-free, iff Θ does not attack itself.
• defends a set Λ ⊆∆, if Λ- ⊆ Θ+.
• is admissible, iff Θ is closed, conflict-free, and defends Θ.
• is preferred, iff Θ is ⊆-maximally admissible.
• is complete, iff Θ is admissible and contains all the assumptions that it defends.
• is well-founded, iff Θ is the intersection of all the complete sets of ABF.
• is grounded, iff Θ is ⊆-minimally complete.

We write Prf(ABF), WF(ABF), Grd(ABF) for, respectively, the set of preferred, well-founded, and grounded sets of assumptions in ABF.

When the rule pr is added to the framework (i.e., ABF′ = (({p, q, r}, { q ¬r , pr }), ∅, {p, q, r}, ¬)), the set {p, q} ceases to be well-founded, preferred or grounded, since it is not closed anymore. In fact, ABF′ has no complete extension.

2 The former are sometimes referred to as rule-based and the latter as logic-based systems of argumentation.

3 There are some formulations of ABFs that define attacks on the level of individual arguments. Since attacks are only possible on assumptions, these formulations are equivalent (cf. also [Toni, 2014]).

3 Labelings and Their Algebraic Structure

As noted previously, our purpose is to provide a faithful description of the semantics of ABFs in terms of labeling functions that assign to each assumption a state that describes its semantical status. Such functions are often three-valued (see [Baroni et al., 2021]): the value in means that the argument is accepted, out denotes that it is rejected, and undec is attached to assumptions that cannot be assigned the other strict values.

An alternative representation of these labels [Strass, 2013] is by pairs (a, u) of values a, u ∈ {0, 1}, where a signifies whether the argument is accepted (therefore should be defended) and u indicates that the argument is unrejected (therefore not attacked). In this writing, (1, 1) is associated with in, (0, 0) is associated with out, and (0, 1) corresponds to undec. The fourth value, (1, 0), denoted conf in what follows, represents conflicts or inconsistency. It is sometimes used in 4-valued labelings where conflict-freeness is relaxed [Arieli, 2016].

The four labels may be arranged in an algebraic structure known as a bilattice [Fitting, 2020]. A bilattice L1 ⊙ L2 is obtained by a mixture of two lattices L1 = 〈L1, ≤1〉 and L2 = 〈L2,≤2〉. Its elements are pairs (x, y), where x ∈ L1 and y ∈ L2, that are arranged in two simultaneous lattice orders:

• the truth order ≤t where (x1, y1) ≤t (x2, y2) if x1 ≤1 x2 and y1 ≤2 y2.
• the information order ≤i in which (x1, y1) ≤i (x2, y2) if x1 ≤1 x2 and y1 ≥2 y2.

In our case, both L1 and L2 are the two-valued lattice TWO, in which 0 < 1. The bilattice FOUR = TWO ⊙ TWO that is obtained, is depicted in Figure 2.

As indicated in Example 1, in non-flat ABFs acceptance and inference are different notions: accepting only p and q (i.e., without r) still means inferring r. We therefore propose to treat these notions separately, and accordingly refine the range of the labeling: we trade the acceptance indication (a) in (a, u) by two indications: one depicts whether the assertion can be inferred (i), and the other one signifies if is can be defended (d). As a result, instead of pairs (a, u), the labels are now pairs ((i, d), u), or, somewhat simpler, triples (i, d, u). These labels can still be arranged in a bilattice structure: Since the first component in the four-valued bilattice is split to two alternative components, we actually end-up with an 8-valued bilattice of the form EIGHT = FOUR≤t ⊙TWO, where FOUR≤t is the ≤t-based lattice of FOUR consisting of pairs (i, d) that represent degrees of acceptance: (1, 1) is the maximal value (indicating that the relevant assumption is both inferred and defended), (0, 0) is the minimal element (neither inference nor defense) and the other two values are incomparable. Thus, the trivalent labels (i, d, u) in EIGHT are arranged by the two bilattice orderings described above, where (i, d) is the first element of the pair, and u is the second element - see also Figure 3. 4 In more detail, denoting respectively by ≤4t and ≤2 the order relations on FOUR≤t and on TWO, the two partial orders of EIGHT are the following:

• (i1, d1, u1) ≤8t (i2, d2, u2) iff (i1, d1) ≤4t (i2, d2) (that is, i1 ≤2 i2 and d1 ≤2 d2) and u1 ≤2 u2.
• (i1, d1, u1) ≤8i (i2, d2, u2) iff (i1, d1) ≤4t (i2, d2) (that is, i1 ≤2 i2 and d1 ≤2 d2) and u1 ≥2 u2.

Note that in four labels in EIGHT the first and second component are identical (i.e., inference and defense coincide), so they preserve the original meaning of the corresponding elements in FOUR. We thus keep their names: in corresponds to (1, 1, 1), out to (0, 0, 0), conf to (1, 1, 0), and undec to (0, 0, 1). The triple (1, 0, 0) corresponds to a contradictory situation (the assertion is inferred but at the same time rejected but not defended), thus it is denoted in what follows by cont. The triple (1, 0, 1) represents a dissonant situation, in which the assertion is inferred and not rejected, but for some reason it is not defended. This triplet is therefore denoted dis.

In what follows, somewhat abusing the notations, we shall identify algebraic structures like EIGHT with their elements. The two following subsets (and the corresponding substructures) of EIGHT will have an important role in the sequel:

4 The highlighted elements are those referred to in Proposition 3.

• SIX = {in, out, undec, dis, cont, conf},
• FIVE = {in, out, undec, dis, cont}.

Intuitively, SIX consists of all values where defended assumptions are also implied, whereas FIVE additionally excludes the conflicting value. Note that the substructure of EIGHT with the elements in SIX is also a bilattice, while the subsctucture with the elements in FIVE is a meet-semibilattice (as the ≤i-join (1, 1, 0) of (1, 0, 0) and (1, 1, 1), is not in FIVE). These algebraic structures are used to define labelling semantics, by assigning to every assumption an element of EIGHT, thus generalizing the idea of 3-valued labellings:

Definition 4. A labeling for ABF = 〈(L,R), Γ,∆,∼〉 is a function l :∆ → EIGHT. A labeling whose range is FIVE (respectively, SIX), is called 5-valued (respectively, 6-valued).

In what follows it will be sometimes convenient to move back and forth between labelings and corresponding triples of subsets of assumption in ∆, called states:

Definition 5. Let ABF = 〈(L,R), Γ,∆,∼〉 be an ABF.

• Given a labeling l, the state sl = (∆i,∆d,∆u), of the inferred, defended and unrejected assumptions in ∆, that is associated with l, is defined by:

A state that is associated with a 5-valued labeling is called consistent.

• Given a state s = (∆i,∆d,∆u), where ∆z ⊆ ∆ for every z ∈ {i, d, u}, the associated labeling ls is defined for every ψ ∈ ∆ by ls (ψ) = (li, ld, lu) where, for every z ∈ {i, d, u}, lz = 1 if ψ ∈ ∆z and lz = 0 otherwise.

Example 4. In the running example (Γ = ∅, ∆ = {p, q, r}, R = { pr , q ¬r }), the state s = ({p, q, r}, {p, q}, {p, q}) represents the intended labelling, where all the assumptions are inferred, but only p and q are unattacked and defended. The associated labeling here is ls (p) = ls (q) = (1, 1, 1) = in and ls (r) = (1, 0, 0) = cont, which reflects the expected interpretation of this case (as discussed in Example 1).

The last example demonstrates that our extended semantics reflects a more fine-grained perspective on the acceptance status of assumptions, allowing a gradual notion of acceptance: assumptions can be both inferred and defended (ls (p) in Example 4), or inferred yet not defended (ls (r) in that example). Next, we show that for this finer granularity (and for desiderata D1-D3) the six-valued bilattice structure SIX suffices.

4 ABF Semantics Based on SIX

We now follow the conventional approach in argumentation theory [Dung, 1995] and introduce a fixpoint operator for defining the semantics of ABFs. According to the intended semantics, the operator transforms between states, consisting of the inferred, defended and non-rejected assertions in ∆.

Definition 6. The operator G :2∆ ×2∆ ×2∆ → 2∆ ×2∆ ×2∆ is defined by G(Θi, Θd, Θu) = (∆i, ∆d, ∆u), where:

• ∆i = {ψ ∈ ∆ | Γ,Θi,Θd ⊢R ψ},
• ∆d = {ψ ∈ ∆ | ψ- ⊆ (Θi ∪ Θd)+},
• ∆u = {ψ ∈ ∆ | ψ ̸∈ (Θi ∪ Θd)+}.

Thus, given a state s = (Θi,Θd,Θu), the operator G constructs a new state (∆i,∆d,∆u) as follows:

• ∆i is the assumptions that can be deduced from the strict premises, the inferred and the defended assumptions in s,
• ∆d is the set of assumptions that are defended (i.e., whose attackers are attacked) by the inferred and defended assumptions in s,
• ∆u consists of the unrejected assumptions, namely all the assumptions that are not attacked by either the inferred or the defended assumptions in s.

Example 5. Consider again the running example and the state s = ({p, q, r}, {p, q}, {p, q}), representing the intended interpretation of the ABF (Example 4). Note that s is a fixpoint of G, that is: G(s) = s. Indeed,

• ∆i = {p, q, r} since p, q, r are derivable from {p, q, r},
• ∆d = {p, q} since p and q are not attacked thus defended, but r cannot be defended from the attack from {q},
• ∆u = {p, q} since both p and q are not attacked by {p, q, r}, while r is attacked by q ∈ {q, p, r}.

We now extend the order relation ≤8i on EIGHT to labelings (l1,l2) and states (s1,s2) in the usual, pointwise, manner:

• l1 ≤8i l2 iff for every ψ ∈ ∆, l1(ψ) ≤8i l2(ψ).
• s1 ≤8i s2 iff ls1 ≤8i ls2 . 5

The following, alternative characterization of ≤8i is useful: Lemma 1. Let s = (∆i,∆d,∆u) and t = (Θi,Θd,Θu). Then s ≤8i t iff ∆i ⊆ Θi and ∆d ⊆ Θd and ∆u ⊇ Θu. 6

Our semantics is now defined by generalizing the ideas underlying both abstract and assumption-based argumentation:

Definition 7. We say that a state s is:

• admissible, if s ≤i G(s),
• complete, if s = G(s),
• preferred, if s is ≤8i -maximally admissible,
• grounded, if s is ≤8i -minimally complete.

A labelling l is admissible, complete, preferred or grounded if so is its associated state sl .

Example 6. The labeling l(p) = l(q) = in, l(r) = cont (recall Example 4) is complete (and so also admissible) for the running example, since, as shown in Example 5, the state sl = ({p, q, r}, {p, q}, {p, q}) that is associated with l is a fixpoint of G. This is also the unique grounded and preferred labelling in this case.

The labeling lu assigning undec to each assumption is only admissible but not complete with respect to the running example. Indeed, the state that is associated with this labeling is slu = (∅, ∅, {p, q, r}), and it holds that G(slu ) = (∅, {p, q}, {p, q, r}) >i slu .

5 Recall from Definition 5 that ls is the labeling function that is associated with the state s.

6 Due to short of space, proofs of some results are delayed to the full version of the paper.

The next example demonstrates the difference between the labels cont and dis:

Example 7. Let ABF = 〈(L, { pr , q ¬r , q ¬q }), ∅, {p, q, r}, ¬〉 be the ABF obtained by adding the rule q ¬q to the running example (see also Figure 4).

Figure 4: A graphical representation of the ABF in Example 7

Again, this ABF doesn't have a complete extension according to the 'classical' semantics in Definition 3. However, the following labeling is a complete extension in our semantics: l = ({p, r}, {p}, {p, q, r}). According to this labeling, we are dissonant about r: l(r) = (1, 0, 1) = dis. This is to be contrasted with the label cont assigned of r in the running example (see Examples 4 and 6), indicating that the evidences concerning r are not robust. The intuitive reason for this modification is that now the attacker q of r becomes less reliable, due to the additional rule, and so the 'balance' between the positive and the negative evidence concerning r is broken.

Next, we show that complete labelings are in fact 6-valued, i.e., they are onto SIX.

Proposition 1. Let s be a compete state. Then for every ψ ∈ ∆, ls (ψ) ∈ SIX.

Proof. Given s state s = (Θi, Θd, Θu) s.t. G(s) = s. We show that ls (ψ) ̸∈ {(0, 1, 0), (0, 1, 1)} for every ψ ∈ ∆. Otherwise, ls (ψ) = (0, 1, x) for x ∈ {0, 1}. Thus, ψ ∈ Θd, and since ⊢R is reflexive, Γ,Θi,Θd ⊢R ψ. Thus, if G(Θi,Θd,Θu) = (∆i,∆d,∆u), we have that ψ ∈ ∆i. Now, since s = G(s), ∆i = Θi, and so ψ ∈ Θi. But this is a contradiction to the assumption that ls (ψ) ∈ {(0, 1, 0), (0, 1, 1)}.

4.1 Fixpoint Computations

Next, we show that the grounded labeling of an ABF can be computed by a standard (polynomial time) iterative process of continuously applying the operator G. Moreover, the labeling that is obtained is 5-valued, meaning that if an assumption is defended, then it is inferred and not rejected. First, we indicate some useful results.

Lemma 2. G is a ≤8i -monotonic operator, that is: if s1 ≤8i s2 then G(s1) ≤8i G(s2).

Corollary 1. If s is admissible then so is G(s).

In what follows, we denote the ≤8i -minimal state (∅, ∅, ∆) of the state-based lattice (2∆ ×2∆ ×2∆,≤8i ) by s⊥, and write G i (s⊥) for the state obtained by i applications of G on s⊥. The next result shows that (unlike classical semantics for non-flat ABFs), the grounded labeling is unique, guaranteed to exist, and can be constructed iteratively.

Proposition 2. Let ABF = 〈(L,R), Γ,∆,∼〉 be an ABF. Then G∞(s⊥) is the unique grounded extension of ABF. If ∆ is finite, then there is an m ∈ N s.t. Gm(s⊥) is the unique grounded extension of ABF.

Proof. We note, first, the following:

Now, for the proposition, we produce a sequence of states s⊥, G(s⊥), G 2 (s⊥), . . .. Since G is ≤8i -monotonic (Lemma 2), and (2∆ × 2∆ × 2∆, ≤8i ) is complete (Lemma 3), by Cousot and Cousot [1979], G∞(s⊥) is the ≤i-minimal fixpoint of G.

If ∆ is finite, then (2∆ ×2∆ ×2∆,≤8i ) is a finite lattice. In that case the construction sequence is finite, thus there is an m ∈ N s.t. Gm(s⊥) is the unique grounded extension.

The next example illustrates the process of computing the grounded extension.

Example 8. Consider again our running example with Γ = ∅, ∆= {p, q, r}, and R= { pr , q ¬r }.

1. The initial state S⊥ = (∆0i ,∆0d ,∆0u ) = (∅, ∅, {p, q, r}), corresponding to the labeling that is uniformly undecided: lS⊥ (p) = lS⊥ (q) = lS⊥ (r) = (0, 0, 1) = undec.
2. Since Γ = ∆0i = ∆0d = ∅, no formula in ∆ can be inferred from the union of these sets, and so ∆1i = ∅. Now, since p- = q- = ∅ , we have that ∆1d = {p, q}. The fact ∆0i ∪∆0d = ∅ also implies that ∆1u = ∆. It follows that G(S⊥) = (∅, {p, q}, {p, q, r}).
3. From∆1d = {p, q} any formula in ∆ can be inferred, thus ∆2i = ∆. Also, we still have that ∆2d = {p, q}. Since r is attacked by q, it holds that ∆2u = {p, q}. Hence, G 2 (S⊥) = ({p, q, r}, {p, q}, {p, q}).

It is easy to check that sg = G 2 (S⊥) is the (least) fixpoint of G. The corresponding labeling function is lsg (p) = lsg (q) = (1, 1, 1) = in, lsg (r) = (1, 0, 0) = cont, meaning that both p and q are accepted in this case while r is contradictory, as indeed expected (cf. Examples 4 and 6).

Next, we show that the grounded labelling is 5-valued:

Proposition 3. Let g be the grounded state of ABF = 〈(L, R), Γ, ∆, ∼〉. Then for every ψ ∈ ∆, lg (ψ) ∈ FIVE.

Proof. We first show the following two lemmas:

Proof. We show this by induction on j. The base step is clear, as ∆0i = ∅. For the inductive step, suppose that ∆ji = {ψ ∈ ∆ | Γ,∆j-1 d ⊢R ψ} and let ψ′ ∈ ∆j+1 i . By the definition of G, then, Γ,∆ji ,∆jd ⊢R ψ′ . This implies, by the inductive hypothesis, that {ψ ∈ ∆ | Γ,∆j-1 d ⊢R ψ},∆jd ⊢R ψ′ . By the transitivity of ⊢R, we get Γ, ∆j-1 d ,∆jd ⊢R ψ′ . Since G is ≤i-monotonic (Lemma 2), by Lemma 1, ∆j-1 d ⊆∆jd , and so Γ,∆jd ⊢R ψ′ . This implies that ∆j+1 i ⊆ {ψ ∈ ∆ | Γ,∆jd ⊢R ψ}. The converse follows from the definition of G.

Lemma 5. For any j ∈ N, let G j (s⊥) = (∆ji ,∆jd ,∆ju ). Then ∆jd ⊆ ∆ju .

Proof. Again, we show the lemma by induction on j. The base step is immediate, as ∆0d = ∅ ⊆ ∆ = ∆0u . For the inductive step, suppose that ∆jd ⊆ ∆ju and, for a contradiction, let ψ ∈ ∆j+1 d \∆j+1 u . As ψ ̸∈ ∆j+1 u , we have Γ,∆ji ∪∆jd ⊢R ∼ψ, which implies, by Lemma 4, that Γ,∆j-1 d ,∆jd ⊢R ∼ψ. By the ≤i-monotonicity of G (Lemma 2) and by Lemma 1, Γ,∆jd ⊢R ∼ψ. Again by Lemma 4, ∆jd is closed under R. Thus, ∆jd ∈ ψ+, which implies by the definition of G and since ψ ∈ ∆j+1 d , that Γ,∆ji ,∆jd ⊢R ∼ψ′ for some ψ′ ∈ ∆jd . By Lemma 4 and the ≤i-monotonicity of G, Γ, ∆jd ⊢R ∼ψ′ . As ψ′ ∈ ∆jd , by the definition of G, Γ, ∆j-1 i , ∆j-1 d ⊢R ∼ψ′′ for some ψ′′ ∈ ∆jd . This means (by the same line of reasoning as above) that Γ,∆j-1 d ⊢R ∼ψ′′ . But then ψ′′ ̸∈ ∆ju (by the definition of G), a contradiction to the inductive hypothesis (i.e., that ∆jd ⊆ ∆ju ) and the fact that ψ′′ ∈ ∆jd .

Proposition 3 now follows from Proposition 1 (implying that lg is 6-valued) and Lemma 5 (excluding the value conf).

As shown next, complete non-grounded states may be sixvalued, as the value conf (i.e., (1, 1, 0)) can be obtained.

Example 9. Let Γ = ∅, ∆ = {p, q} and R = { p ¬q }. Then the state s = ({p, q}, {p, q}, {p}) is complete, since G(s) = s. The labeling of this state is not onto FIVE, since ls (q) = conf.

Observe the difference between the values conf and cont: In Example 6, r is both inferred and rejected but not defended, thus it is assigned the value cont. Here, q is also inferred and rejected, but now it is also defended, thus it is assigned the value conf (denoting a higher conflicting measure).

5 Some Basic Properties

In this section we show that desiderata D1, D2 and D3 from the introduction are satisfied by our semantics. We have already partially considered D3, showing that the grounded labelling is unique, guaranteed to exist and iteratively constructible. Next, we show another property that holds for the standard semantics of flat ABFs but not always for non-flat ABFs: every preferred extension is also complete.

Proposition 4. Let ABF = 〈(L, R), Γ, ∆, ∼〉 be an ABF. If s is a preferred state then it is complete.

Proof. Suppose that s is a preferred labelling. Then s ≤i G(s). Suppose now towards a contradiction that s ̸= G(s) (which implies that s <i G(s)). Since G is ≤i-monotonic, G(s) ≤i G 2 (s), i.e, G(s) is also admissible. But then we have found a witness (G(s)) against the ≤i-maximality of s.

Turning to desiderata D1 and D2, we now show that the set of complete labellings extends the (classical) complete extensions, and coincides with them if the ABF is flat:

Proposition 5. Let ABF = 〈(L,R), Γ,∆,∼〉 be an ABF. If Θ is a complete extension of ABF (Definition 3), (Θ, Θ, ∆\Θ+) is a consistent complete state for ABF. If ABF is flat, then the converse also holds: if (Θ,Θ,∆ \ Θ+) is a consistent complete state for ABF then Θ is a complete extension of ABF.

Proof. [⇒]: Suppose that Θ is a complete extension. (1) As Θ is closed, we have that Γ, Θ ⊢R ψ iff ψ ∈ Θ. (2) As Θ is complete, ψ ∈ Θ iff ψ is defended by Θ. (3) By definition,

∆ \ Θ+ = {ψ ∈ ∆ | ψ- ∩ Θ = ∅}. By (1)-(3), the triple

(Θ, Θ, ∆ \ Θ+) is a consistent complete state for ABF. [⇐]: Suppose that (Θ,Θ,∆ \ Θ+) is a consistent complete state for ABF and ABF is flat. We have to show that Θ is conflict-free, defended, and contains all the assumptions it defends. Conflict-freeness follows from the fact that, by the definition of G, ∆ \ Θ+ = {φ ∈ ∆ | φ- ∩ Θ = ∅} and since Θ ⊆ ∆ \ Θ+ (which we know since we assumed consistency). Likewise, the fact that Θ = {φ ∈ ∆ | φ- ⊆ Θ+} immediately implies that φ ∈ Θ iff φ is defended by Θ.

Note 2. The next example shows that not every complete (non-classical) labelling corresponds to a classical complete extension, even if the ABF has classical complete extensions.

Example 10. Let R = { pr , p ¬q , q ¬p , q ¬r , r ¬r }, Γ = ∅, and ∆ = {p, q, r}. A diagram of this ABF appears in Figure 5.

{q} is the unique classical complete extension of the ABF. By Proposition 5, {q} corresponds to the state ({q}, {q}, {q}). Yet, the state ({p, r}, {p}, {p}) is also complete.

The coincidence of complete extensions carries over to preferred/grounded extensions for flat ABFs.

Proposition 6. Let ABF = 〈(L,R), Γ,∆,∼〉 be a flat ABF. Then Θ is a [preferred/grounded] extension of ABF (according to Definition 3) iff (Θ,Θ,∆ \ Θ+) is a consistent [preferred/grounded] state for ABF.

Proof. Suppose that Θ is a preferred extension of ABF. Then it is a maximally complete extension (this is shown in [Bondarenko et al., 1997]), which means, with Proposition 5 that (Θ,Θ,∆ \ Θ+) is a consistent complete state. Suppose now that (Θ, Θ, ∆ \ Θ+) is not preferred, which means (with Proposition 4) that there is some (Θ′ ,Θ′ ,∆ \ Θ′+) >i (Θ,Θ,∆ \ Θ+) that is complete. This means that Θ ⊆ Θ′ and ∆ \ Θ′+ ⊆ ∆ \ Θ+ (the latter simply means again that Θ ⊆ Θ′ ), and one of these inclusions is proper, which altogether means that Θ ⊂ Θ′ . Also, as (Θ′ ,Θ′ ,∆ \ Θ′+) is complete, by Proposition 4, Θ′ is complete. But this contradicts Θ being preferred.

The ⇐-direction and the case for grounded semantics are similar.

Note 3. The last results immediately imply that the grounded state s g = (∆g i ,∆g d , ∆g u ) approximates any classical complete extension s = (Θ,Θ,∆\Θ+), in the sense that s g ≤8i s.

Finally, we show that the grounded state and the wellfounded extension are incomparable:

Example 11. Let Γ = ∅, ∆ = {p}, and R = { p , p ¬p } (see Figure 6, left). Then the grounded state is ({p}, ∅, ∅). As there are no classical complete extensions, the wellfounded extension is ∅, corresponding to the state (∅, ∅, ∅). Thus, in this case, the grounded state is more informative (as (∅, ∅, ∅) ≤8i ({p}, ∅, ∅)).

Example 12. Consider Γ = ∅, ∆ = {p, q, r, s}, and R = { p ¬q , q ¬p , p ¬s , q ¬s , s ¬r , r } (Figure 6, right). There are two (classically) complete extensions in this case: {p, r} and {q, r}. Thus, the well-founded extension is {r} (corresponding to the state ({r}, {r}, {p, q, r, s})). The grounded state, on the other hand, is ({r}, ∅, {p, q, r, s}). Hence, in this case, the well-founded extension is more informative than the grounded state (as ({r}, ∅, {p, q, r, s}) ≤8i ({r}, {r}, {p, q, r, s})).

5.1 Computational Complexity

We now investigate the complexity of reasoning tasks associated with the new semantics. We assume familiarity with standard complexity concepts, including oracles and the polynomial hierarchy. First,we note the following:

Note 4. By Propositions 2 and 4, the verification (existence) problem (i.e., checking whether an ABF admits a complete, grounded or preferred state) is trivial.

For studying the complexity of computing states and labeling, we assume that R consists only of Horn-rules, namely, rules of the form p1, ..., pn q , where pi (1 ≤ i ≤ n) are atomic formulas and q is either an atomic formula or the propositional constant for falsity. ABFs with only Horn rules are called Horn-ABFs [ ˇCyras et al., 2021].

Lemma 6. InHorn-ABFs, G(s) can be computed froma state s in polynomial time.

Proof. Let s = (Θi,Θd,Θu) and G(s) = (∆i,∆d,∆u).

We first recall that derivation of consequences of a Hornrule set is in P. Thus, ∆i is computed in polynomial time.

To compute ∆u we need to check for every ψ ∈ ∆ whether Γ,Θi,Θd ⊢R ∼ψ. This requires O(|∆|) polynomial checks (of ⊢R), which is again polynomial.

Finally, ∆\∆d is calculated by: (1) calculating (Θi ∪Θd)+ by checking for every ψ ∈ ∆ whether Γ,Θi ∪ Θd ⊢R ∼ψ (so O(|∆|) ⊢R-checks), and (2) checking for every φ ∈ ∆ whether Γ,∆ \ (Θi ∪ Θd)+ ⊢R ∼ψ (so again O(|∆|) ⊢Rchecks). As ∆\∆d can be calculated in polynomial time, we have also determined ∆d in polynomial time.

Corollary 2. Checking whether a state s is complete for a Horn-ABF is in P.

Proof. Since by Lemma 6 the computation of G(s) is polynomial, so is the checking whether s = G(s).

Proposition 7. Computing the grounded state for a HornABF is in P and checking whether a state s is preferred for a Horn-ABF is coNP-complete.

Proof. The claim concerning the grounded state (and the corresponding grounded labeling) follows from Proposition 2 and its proof, showing that the grounded extension can be computed by m ∈ N iterations of applying the G operator on given states, starting from s⊥. By Lemma 6, each such application is computable in polynomial time.

Concerning the preferred semantics, membership is shown as follows: one can check whether s is not preferred by first checking whether it is complete (this is polynomial by Corollary 2) and then guessing a state s′ >i s and verifying that it is complete (again, this is polynomial). Hardness follows from the fact that flat ABFs are a special case (Proposition 6) and by [Dimopoulos et al., 2002, Theorem 14].

The last results imply that the computational complexity of all the reasoning tasks considered here is preserved when moving from flat ABFs under the classical semantics to nonflat ABFs under the labeling and state semantics introduced in this paper. This stands in contrast to the classical semantics for non-flat ABFs, which, as shown in [ ˇCyras et al., 2021], result in an increased complexity for all these reasoning tasks (namely, coNP-complete for skeptical grounded reasoning, DP-complete for verifying completeness and ΠP2 -complete for verifying preferedness).

6 Summary, RelatedWork, and Conclusion

We introduced an 8-valued bilattice-based labeling semantics for assumption-based argumentation frameworks that overcomes some anomalies of the standard 3-valued semantics for such frameworks. In particular, this labeling enables several degrees of acceptance and as a consequence it is capable of accepting, to different levels, every inferred assertion. Following Dung's original method of providing semantics to argumentation frameworks by fixpoints of operators, we formulated semantics which preserve the semantics of flat ABFs, extend the classical semantics of non-flat ABFs, and satisfy all the usual properties of argumentative semantics.

Non-flat ABFs have been studied in relation to other formalisms, such as autoepistemic logic [Bondarenko et al., 1997] and bipolar argumentation [ ˇCyras et al., 2017]. In future work we will investigate these translations in our semantics. Some complexity results for classical semantics of non-flat ABFs appear in [ ˇCyras et al., 2021]. Many of the problems for classical semantics for non-flat ABFs have been noted elsewhere (see, e.g., [ ˇCyras et al., 2018]), and our list of desiderata is based on such problems. To the best of our knowledge, this is the first proposal for an alternative semantics for non-flat ABFs, which copes with such problems.

Future work involves a number of issues, such as the considerations of further argumentative semantics (e.g., the stable, ideal and semi-stable semantics). Another interesting issue for future explorations is the providing of constructive ways of computing labelings other than the grounded labeling. One way of doing so is by expressing the labeling assignments in terms of theories consisting of formal rules (e.g., as in [Arieli and Caminada, 2013]). This then allows to use off-the-shelf solvers for computing the labelings (see, for instance, [Cerutti et al., 2017; Besnard et al., 2020]).

Acknowledgments

The second author is partially supported by the Israel Science Foundation, grant No. 550/19.