# semantics_for_nonflat_assumptionbased_argumentation_revisited__874df9a2.pdf Semantics for Non-Flat Assumption-Based Argumentation, Revisited Jesse Heyninck1,2 and Ofer Arieli3 1Department of Computer Science, Open Universiteit, Heerlen, the Netherlands 2University of Cape Town and CAIR, South-Africa 3School of Computer Science, Tel-Aviv Academic College, Tel-Aviv, Israel jesse.heyninck@ou.nl, oarieli@mta.ac.il Assumption-based argumentation (ABA) is an argumentative formalism that allows for reasoning on the basis of defeasible assumptions and strict rules. Standard semantics for this formalism sometimes give rise to problematic behaviour in the presence of rules with assumptions in their heads. In this paper, we introduce a six-valued labelling semantics that overcomes these shortcomings while preserving all the usual properties of the standard Dung-style three-valued semantics for ABA frameworks, including existence of the complete semantics, uniqueness of the grounded semantics, and preservation of the computational complexity of all the main reasoning processes. 1 Introduction and Motivation 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). Figure 1: A graphical representation of the ABF in Example 1. Dotted arrows represent inference and full arrows represent attacks 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- Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) 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 ψ1, . . . , ψn ψ (or: ψ1, . . . , ψn ψ) 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 R whose 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 = { p r}, and ψ = ψ for every ψ .1 Conflicts (attacks) between sets of defeasible assumptions are defined as follows: 1In 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. Example 3. Let ABF = (({p, q, r}, { q r}), , {p, q, r}, ). Then WF(ABF) = Prf(ABF) = Grd(ABF) = {{p, q}}. When the rule p r is added to the framework (i.e., ABF = (({p, q, r}, { q r }), , {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. 2The former are sometimes referred to as rule-based and the latter as logic-based systems of argumentation. 3There 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]). Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) 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. (0, 1) undec (0, 0) out (1, 1) in (1, 0) conf Figure 2: FOUR 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 4 t and 2 the order relations on FOUR t and on TWO, the two partial orders of EIGHT are the following: (i1, d1, u1) 8 t (i2, d2, u2) iff (i1, d1) 4 t (i2, d2) (that is, i1 2 i2 and d1 2 d2) and u1 2 u2. (i1, d1, u1) 8 i (i2, d2, u2) iff (i1, d1) 4 t (i2, d2) (that is, i1 2 i2 and d1 2 d2) and u1 2 u2. (0, 0, 1) undec (0, 0, 0) out (1, 0, 0) cont (1, 1, 0) conf (1, 0, 1) dis (0, 1, 0) (1, 1, 1) in Figure 3: EIGHT 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: 4The highlighted elements are those referred to in Proposition 3. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) 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: i = {ψ | l(ψ) = (1, x, y) for x, y {0, 1}} d = {ψ | l(ψ) = (x, 1, y) for x, y {0, 1}} u = {ψ | l(ψ) = (x, y, 1) for x, y {0, 1}} 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 = { p 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 8 i on EIGHT to labelings (l1,l2) and states (s1,s2) in the usual, pointwise, manner: l1 8 i l2 iff for every ψ , l1(ψ) 8 i l2(ψ). s1 8 i s2 iff ls1 8 i ls2. 5 The following, alternative characterization of 8 i is useful: Lemma 1. Let s = ( i, d, u) and t = (Θi, Θd, Θu). Then s 8 i 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 8 i -maximally admissible, grounded, if s is 8 i -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. 5Recall from Definition 5 that ls is the labeling function that is associated with the state s. 6Due to short of space, proofs of some results are delayed to the full version of the paper. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) The next example demonstrates the difference between the labels cont and dis: Example 7. Let ABF = (L, { p 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 8 i -monotonic operator, that is: if s1 8 i s2 then G(s1) 8 i G(s2). Corollary 1. If s is admissible then so is G(s). In what follows, we denote the 8 i -minimal state ( , , ) of the state-based lattice (2 2 2 , 8 i ) by s , and write Gi(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: Lemma 3. (2 2 2 , 8 i ) is a complete lattice. Now, for the proposition, we produce a sequence of states s , G(s ), G2(s ), . . .. Since G is 8 i -monotonic (Lemma 2), and (2 2 2 , 8 i ) 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 , 8 i ) 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 = { p (0) The initial state S = ( 0 i , 0 d, 0 u) = ( , , {p, q, r}), corresponding to the labeling that is uniformly undecided: l S (p) = l S (q) = l S (r) = (0, 0, 1) = undec. (1) Since Γ = 0 i = 0 d = , no formula in can be inferred from the union of these sets, and so 1 i = . Now, since p = q = , we have that 1 d = {p, q}. The fact 0 i 0 d = also implies that 1 u = . It follows that G(S ) = ( , {p, q}, {p, q, r}). (2) From 1 d = {p, q} any formula in can be inferred, thus 2 i = . Also, we still have that 2 d = {p, q}. Since r is attacked by q, it holds that 2 u = {p, q}. Hence, G2(S ) = ({p, q, r}, {p, q}, {p, q}). It is easy to check that sg = G2(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: Lemma 4. For any 1 j N, let Gj(s ) = ( j i , j d, j u). Then: j i = {ψ | Γ, j 1 d R ψ}. Proof. We show this by induction on j. The base step is clear, as 0 i = . For the inductive step, suppose that j i = {ψ | Γ, j 1 d R ψ} and let ψ j+1 i . By the definition of G, then, Γ, j i , j d R ψ . This implies, by the inductive hypothesis, that {ψ | Γ, j 1 d R ψ}, j d R ψ . By the transitivity of R, we get Γ, j 1 d , j d R ψ . Since G is i-monotonic (Lemma 2), by Lemma 1, j 1 d j d, and so Γ, j d R ψ . This implies that j+1 i {ψ | Γ, j d R ψ}. The converse follows from the definition of G. Lemma 5. For any j N, let Gj(s ) = ( j i , j d, j u). Then j d j u. Proof. Again, we show the lemma by induction on j. The base step is immediate, as 0 d = = 0 u. For the inductive step, suppose that j d j u and, for a contradiction, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) let ψ j+1 d \ j+1 u . As ψ j+1 u , we have Γ, j i j d R ψ, which implies, by Lemma 4, that Γ, j 1 d , j d R ψ. By the i-monotonicity of G (Lemma 2) and by Lemma 1, Γ, j d R ψ. Again by Lemma 4, j d is closed under R. Thus, j d ψ+, which implies by the definition of G and since ψ j+1 d , that Γ, j i , j d R ψ for some ψ j d. By Lemma 4 and the i-monotonicity of G, Γ, j d R ψ . As ψ j d, by the definition of G, Γ, j 1 i , j 1 d R ψ for some ψ j d. This means (by the same line of reasoning as above) that Γ, j 1 d R ψ . But then ψ j u (by the definition of G), a contradiction to the inductive hypothesis (i.e., that j d j u) and the fact that ψ j d. 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 (Θ, Θ, \ Θ+) 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 sg = ( g i , g d, g u) approximates any classical complete extension s = (Θ, Θ, \ Θ+), in the sense that sg 8 i 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 ( , , ) 8 i ({p}, , )). Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Example 12. Consider Γ = , = {p, q, r, s}, and R = { p 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}) 8 i ({r}, {r}, {p, q, r, s})). Figure 6: Representations of the ABFs in Example 11 (left) and Example 12 (right) 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. In Horn-ABFs, G(s) can be computed from a 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 Horn ABF is in P and checking whether a state s is preferred for a Horn-ABF is co NP-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, co NP-complete for skeptical grounded reasoning, DP-complete for verifying completeness and ΠP 2-complete for verifying preferedness). 6 Summary, Related Work, 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]). Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Acknowledgments The second author is partially supported by the Israel Science Foundation, grant No. 550/19. References [Arieli and Caminada, 2013] Ofer Arieli and Martin W. Caminada. A QBF-based formalization of abstract argumentation semantics. Journal of Applied Logic, 11(2):229 252, 2013. [Arieli and Straßer, 2015] Ofer Arieli and Christian Straßer. Sequent-based logical argumentation. Journal of Argument and Computation, 6(1):73 99, 2015. [Arieli, 2016] Ofer Arieli. On the acceptance of loops in argumentation frameworks. Journal of Logic and Computation, 26(4):1203 1234, 2016. [Arieli, 2022] Ofer Arieli. Four-valued semantics for abstract argumentation frameworks using (extensions of) Dunn Belnap four-valued logic, volume 46 of Tributes, Essays in honor of J. M. Dunn. College Publications, 2022. [Baroni et al., 2018] Pietro Baroni, Dov Gabbay, Massimiliano Giacomin, and Leendert van der Torre. Handbook of Formal Argumentation, volume 1. College Publications, 2018. [Baroni et al., 2021] Pietro Baroni, Martin Caminada, and Massimiliano Giacomin. Abstract argumentation frameworks and their semantics. In Dov Gabbay, Massimiliano Giacomin, Guillermo Simari, and Matthias Thimm, editors, Handbook of Formal Argumentation, volume 2. College Publications, 2021. [Besnard and Hunter, 2001] Philippe Besnard and Anthony Hunter. A logic-based theory of deductive arguments. Artificial Intelligence, 128(1):203 235, 2001. [Besnard et al., 2020] Philippe Besnard, Claudette Cayrol, and Marie-Christine Lagasquie-Schiex. Logical theories and abstract argumentation: A survey of existing works. Journal of Argument & Computation, 11(1-2):41 102, 2020. [Bistarelli and Taticchi, 2021] Stefano Bistarelli and Carlo Taticchi. A unifying four-state labelling semantics for bridging abstract argumentation frameworks and belief revision. In Proceedings of the 22nd Italian Conference on Theoretical Computer Science (ICTCS 21), volume 3072 of CEUR Workshop Proceedings, pages 93 106, 2021. [Bondarenko et al., 1997] Andrei Bondarenko, Phan Minh Dung, Robert Kowalski, and Francesca Toni. An abstract, argumentation-theoretic approach to default reasoning. Artificial Intelligence, 93(1):63 101, 1997. [Cerutti et al., 2017] Federico Cerutti, Sarah Alice Gaggl, Matthias Thimm, and Johannes Peter Wallner. Foundations of implementations for formal argumentation. Journal of Applied Logics-If Co Log Journal of Logics and their Applications, 4(8):2623 2706, 2017. [Cousot and Cousot, 1979] Patrick Cousot and Radhia Cousot. Constructive versions of Tarski s fixed point theorems. Pacific journal of Mathematics, 82(1):43 57, 1979. [ ˇCyras et al., 2017] Kristijonas ˇCyras, Claudia Schulz, and Francesca Toni. Capturing bipolar argumentation in nonflat assumption-based argumentation. In International Conference on Principles and Practice of Multi-Agent Systems, pages 386 402. Springer, 2017. [ ˇCyras et al., 2018] Kristijonas ˇCyras, Xiuyi Fan, Claudia Schulz, and Francesca Toni. Assumption-based argumentation: Disputes, explanations, preferences. Handbook of Formal Argumentation, pages 2407 2456, 2018. [ ˇCyras et al., 2021] Kristijonas ˇCyras, Quentin Heinrich, and Francesca Toni. Computational complexity of flat and generic assumption-based argumentation, with and without probabilities. Artificial Intelligence, 293:103449, 2021. [Dimopoulos et al., 2002] Yannis Dimopoulos, Bernhard Nebel, and Francesca Toni. On the computational complexity of assumption-based argumentation for default reasoning. Artificial Intelligence, 141(1/2):57 78, 2002. [Dung et al., 2009] Phan Minh Dung, Robert Kowalski, and Francesca Toni. Assumption-based argumentation. In Iyad Rahwan and Guillermo Simari, editors, Argumentation in Artificial Intelligence, pages 199 218. Springer, 2009. [Dung, 1995] Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77:321 358, 1995. [Fitting, 2020] Melvin Fitting. Bilattice basics. If Co Log Journal of Logics and their Applications, 7(6):973 1016, 2020. [Gabbay et al., 2021] Dov Gabbay, Massimiliano Giacomin, Guillermo Simari, and Matthias Thimm. Handbook of Formal Argumentation, volume 2. College Publications, 2021. [Garc ıa and Simari, 2004] Alejandro Garc ıa and Guillermo Simari. Defeasible logic programming: An argumentative approach. Theory and Practice in Logic Programming, 4(1-2):95 138, 2004. [Jakobovits and Vermeir, 1999] Hadassa Jakobovits and Dirk Vermeir. Robust semantics for argumentation frameworks. Journal of Logic and Computation, 9(2):215 261, 1999. [Modgil and Prakken, 2014] Sanjay Modgil and Henry Prakken. The ASPIC+ framework for structured argumentation: a tutorial. Argument and Computation, 5(1):31 62, 2014. [Schulz and Toni, 2017] Claudia Schulz and Francesca Toni. Labellings for assumption-based and abstract argumentation. J. Approximate Reasoning, 84:110 149, 2017. [Strass, 2013] Hannes Strass. Approximating operators and semantics for abstract dialectical frameworks. Artificial Intelligence, 205:39 70, 2013. [Toni, 2014] Francesca Toni. A tutorial on assumption-based argumentation. Journal of Argument and Computation, 5(1):89 117, 2014. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)