# conditional_abstract_dialectical_frameworks__3011178a.pdf

Conditional Abstract Dialectical Frameworks

Jesse Heyninck1,2, Matthias Thimm3, Gabriele Kern-Isberner1, Tjitze Rienstra4, Kenneth Skiba3

1Technische Universit at Dortmund, Dortmund, Germany 2University of Cape Town and CAIR, South-Africa 3Fern Universit at Hagen, Hagen, Germany 4Maastricht University, Maastricht, The Netherlands

Abstract dialectical frameworks (in short, ADFs) are a unifying model of formal argumentation, where argumentative relations between arguments are represented by assigning acceptance conditions to atomic arguments. This idea is generalized by letting acceptance conditions being assigned to complex formulas, resulting in conditional abstract dialectical frameworks (in short, c ADFs). We define the semantics of c ADFs in terms of a non-truth-functional four-valued logic, and study the semantics in-depth, by showing existence results and proving that all semantics are generalizations of the corresponding semantics for ADFs.

1 Introduction

Formal argumentation is one of the major approaches to knowledge representation. In the seminal paper (Dung 1995), abstract argumentation frameworks were conceived of as directed graphs where nodes represent arguments and edges between these nodes represent attacks. So-called argumentation semantics determine which sets of arguments can be reasonably upheld together given such an argumentation graph. Various authors have remarked that other relations between arguments are worth consideration. For example, in (Cayrol and Lagasquie-Schiex 2005), bipolar argumentation frameworks are developed, where arguments can support as well as attack each other. The last decades saw a proliferation of such extensions of the original formalism of (Dung 1995), and it has often proven hard to compare the resulting different dialects of the argumentation formalisms. To cope with the resulting multiplicity, (Brewka et al. 2013) introduced abstract dialectical frameworks (in short, ADFs) that aims to unify these different dialects (Polberg 2016). Just like in (Dung 1995), ADFs are directed graphs. In difference to abstract argumentation frameworks, however, in ADFs, edges between nodes do not necessarily represent attacks but can encode any relationship between arguments. Such a generality is achieved by associating an acceptance condition with each argument, which is a Boolean formula in terms of the parents of the argument that expresses the conditions under which an argument can be accepted. This results in an ADF being defined as a triple

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

(At, L, C) where At represents a set of atoms or arguments, L At At represents a set of argumentative relations between the atoms and C is a set of acceptance conditions Cs for every s At. As such, ADFs are able to capture all of the major semantics of abstract argumentation and offer a general framework for argumentation-based inference. Furthermore, ADFs were shown to capture logic programming (Brewka et al. 2013). In (Heyninck et al. 2019), first attempts were made to translate non-monotonic conditional logics in ADFs. However, there are limits to the representative capabilities of ADFs, both on a conceptual as well as a more technical level. On the conceptual level, acceptance conditions are assigned to atoms, which means that, e. g., an attack on a set of arguments cannot be captured by ADFs. For example, to state that the set {p, q} is attacked by r we would have to be able to set the acceptance condition of p q to r, which is not possible in ADFs. Likewise, it is not immediately obvious how to represent more complicated logic programming languages in ADFs, such as disjunctive logic programming. Such limitations are, not unsurprisingly, also reflected on a more technical level. For example, a (polynomial) translation of disjunctive logic programming into ADFs is impossible in view of considerations on complexity. Finally, in (Heyninck et al. 2019) it was shown that only a fragment of the full language of conditional logics can be translated in ADFs in view of their limited syntax. In this paper, we generalize ADFs as to allow for the assignment of acceptance conditions to complex formulas. This results in conditional abstract dialectical frameworks (in short, c ADFs) which are sets of acceptance pairs of the form φ ψ with arbitrary formulas φ and ψ, interpreted as a defeasible version of φ is the case if and only if ψ is the case . The semantics of c ADFs are formulated as a generalization of the semantics of ADFs, with the Γ-function, on its turn based on a non-truth-functional four-valued logic, as a central component. Some of the main results include existence results for all the major semantics, as well as the definition of the so-called grounded state, a single-state semantics which can be iteratively constructed and represents the minimal information entailed by a given c ADF. Outline of this Paper: We first state all the necessary preliminaries in Section 2 on propositional logic (Section 2), and abstract dialectical argumentation (Section 2). The syn-

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

tax of conditional abstract dialectical frameworks c ADFs is introduced in Section 3. In Section 4, a four-valued logic, which will form the basis of the semantics of c ADFs, is defined and studied. In Section 5, we then define and study the admissible, complete, preferred and grounded semantics for c ADFs. A unique, iteratively constructible analogue to the grounded extension, called the grounded state, is introduced in Section 6. Related work is discussed in Section 7 and a conclusion is drawn in Section 8.

2 Preliminaries In the following, we briefly recall some general preliminaries on propositional logic and ADFs (Brewka et al. 2013).

Propositional Logic For a set At of atoms let L(At) be the corresponding propositional language constructed using the usual connectives (and), (or), (negation) and (material implication). A (classical) interpretation (also called possible world) ω for a propositional language L(At) is a function ω : At {T, F}. Let V2(At) denote the set of all interpretations for At. We simply write V2 if the set of atoms is implicitly given. An interpretation ω satisfies (or is a model of) an atom a At, denoted by ω |= a, if and only if ω(a) = T. The satisfaction relation |= is extended to formulas as usual. For Φ L(At) we also define ω |= Φ if and only if ω |= φ for every φ Φ. Define the set of models Mod2(X) = {ω V2(At) | ω |= X} for every formula or set of formulas X. A formula or set of formulas X1 entails another formula or set of formulas X2, denoted by X1 X2, if Mod2(X1) Mod2(X2). A formula φ is a tautology if Mod2(φ) = V2(At) and a falsity if Mod2(φ) = .

Abstract Dialectical Frameworks We briefly recall some technical details on ADFs following loosely the notation from (Brewka et al. 2013). An ADF D is a tuple D = (At, L, C) where At is a finite set of atoms, L At At is a set of links, and C = {Cs}s At is a set of total functions Cs : 2par D(At) { , } for each s At with par D(s) = {s At | (s , s) L} (also called acceptance functions). An acceptance function Cs defines the cases when the statement s can be accepted (truth value ), depending on the acceptance status of its parents in D. By abuse of notation, we will often identify an acceptance function Cs by its equivalent acceptance condition which models the acceptable cases as a propositional formula.

Example 1. We consider the following ADF D1 = ({a, b, c}, L, C) with L = {(a, b), (b, a), (a, c), (b, c)} and Ca = b, Cb = a, and Cc = a b. Informally, the acceptance conditions can be read as a is accepted if b is not accepted , b is accepted if a is not accepted and c is accepted if a or b is not accepted .

An ADF D = (At, L, C) is interpreted through 3-valued interpretations ν : At {T, F, U}. We denote the set of all 3-valued interpretations over At by V3(At). We define the information order <i over {T, F, U} by making U the minimal element: U <i T and U <i F, and i iff

<i or = for any , {T, F, U}. This order is lifted point-wise as follows (given ν, ν V3(At)): ν i ν iff ν(s) i ν (s) for every s At. The set of two-valued interpretations extending a 3-valued interpretation v is defined as [ν]2 = {ω V2(At) | ν i ω}. Given a set of 3-valued interpretations V V3(At), i V is the 3-valued interpretation defined via i V (s) = if for every ν V , ν(s) = , for any {T, F, U}, and i V (s) = U otherwise. Truth values based on a three-valued interpretations can now be assigned to complex formulas φ by taking i[ν]2(φ). All major semantics of ADFs single out three-valued interpretations in which the truth value of every atom s At is, in some sense, in alignment or agreement with the truth value of the corresponding condition Cs. The Γ-function enforces this intuition by mapping an interpretation ν to a new interpretation ΓD(ν), which assigns to every atom s exactly the truth value assigned by v to Cs, i.e.:

ΓD(ν) : At 7 {T, F, U} where s i{ω(Cs) | ω [ν]2}.

Definition 1. Let D = (At, L, C) be an ADF with ν V(At) a 3-valued interpretation. Then: ν is admissible for D iff ν i ΓD(ν); ν is complete for D iff ν = ΓD(ν); ν is preferred for D iff ν is i-maximal among all admissible interpretations; and ν is grounded for D iff ν is i-minimal among all complete interpretations. We denote by adm(D), cmp(D), prf(D), and grnd(D) the sets of complete, preferred, and grounded interpretations of D, respectively.

Notice that ν is admissible iff ν(s) i i[ν]2(Cs) for every s S and likewise, ν is complete iff ν(s) = i[ν]2(Cs) for every s S. It can thus be observed that the logic defined by i[ν]2 is, essentially, the logic underlying ADFs, in the sense that the evaluation of acceptance conditions under i[ν]2 is the fundamental operation underlying every semantical notion of ADFs. It should be furthermore noted that i[ν]2 does not give rise to a truth-functional logic. Recall that a truth-functional logic is a logic in which the truth value assigned to a complex formula is a function of the truth values of its component formulas. E.g. for a truth-functional logic, the truth value of a b is determined completely by the truth value of a and b. For example, given ν(a) = U and ν(b) = U, i[ν]2( a) = U and i[ν]2(a a) = T whereas i[ν]2(a b) = U. Thus, the logic defined by i[ν]2 is not truth-functional.

Example 2 (Ex. 1 ctd.). The ADF in Ex. 1 has three complete models ν1, ν2, ν3 with: ν1(a) = T, ν1(b) = F and ν1(c) = T; ν2(a) = F, ν2(b) = T and ν2(c) = T; and ν3(a) = U, ν3(b) = U, and ν3(c) = U. ν3 is the grounded interpretation whereas ν1 and ν2 are both preferred.

3 Syntax of c ADFs

The syntactical representation D = (S, L, C) of an ADF contains some superfluous information. In particular, as there is a link between a statement s and s iff s is mentioned in the acceptance condition of s , the set of links does not contain any information not already derivable from the set of acceptance conditions C. As such, given a set of atoms S, we can simply write an ADF as a set of statements s Cs

if Cs is the acceptance condition of s. So the ADF D1 from Example 1 can be simply written as:

D1 = {a b, b a, c a b}

An ADF is determined by a set of propositional formulæ that, when evaluated to true, make a certain statement, which is a simple atom, true as well, and when evaluated to false, make the simple atom false as well. In other words, can be read as a approximate if and only if: s Cs means that the truth-values s and Cs should be aligned. can truly be read as a approximate iff, since it might not always be possible to align the truth values of s and Cs in such a way that they take on exactly the same (determinate) truth value. To see this, consider, e. g., a a. We generalise this framework by allowing these statements to be arbitrary propositional formulæ: Definition 2. Given a set of atoms At, a conditional abstract dialectical framework c ADF Π w.r.t. At is a finite set of acceptance pairs over At, where an acceptance pair is of the form:

with φ and ψ being propositional formulæ over At. In order to stick to ADF terminology we call φ the statement and ψ the condition of the acceptance pair φ ψ. We omit the reference to the signature At when it is clear from context. Example 3. Consider a c ADF Π1 = {c1, c2, c3} with

c1 : p s q c2 : p s q c3 : (p q) (p s) t

This c ADF can be used to model an argument of a group of friends about making plans on a Sunday. They are discussing whether to go to a party (p), to the swimming pool (s) or go to a pub quiz (q). They want to do at least one of these three things (c1). However, if they go to the quiz, they won t be able to still go to the pool and go to the party (represented by the attack of q on p s in c2). If everyone arrives on time (t), they would like to go to both the quiz and the party, or to both the pool and the party (c3). We notice that without adding further atoms, an attack from q on the set {p, s}, as formalized by c2, cannot be represented in ADFs. We observe that this simple generalization w.r.t. ADFs results in the following additional points of expressiveness in comparison to ADFs: c ADFs allow for complex formulas as statements, as demonstrated by (p q) (p s) t in Example 3 c ADFs allow for incomplete specifications, i.e. they do not force the user to formulate an acceptance condition for every atom, as demonstrated by the c ADF {a b}, where b has no acceptance condition. c ADFs allow for overspecifications or conflicting specifications, as demonstrated by the c ADF {a b, a b} where both a and a have the acceptance condition b.

c ADFs allow for indeterminism, as demonstrated by the c ADF {a b }, where a b is required to be true, but no further information on which of the disjuncts is required to be true is given. To cope with this higher expressiveness semantically, it will prove useful to move from three-valued interpretations to four-valued interpretations. To assign truth values to complex formulas on the basis of four-valued interpretations, we generalize the logic defined by i[ν]2 to a four-valued setting in Section 4. We then generalize the semantics of ADFs to c ADFs on the basis of this four-valued logic in Section 5.

4 A Four-Valued Logic Based on Completions We first define a four-valued logic 4CM which generalizes the idea of completions known from the logic underlying ADFs defined by [ν]2, which preserves classical tautologies and falsities. We first recall four-valued interpretations. A four-valued interpretation v : At {T, F, I, U} assigns to every atom a truth value T (true), F (false), U (undecided) or I (inconsistent). We will also write an interpretation v V4({a1, . . . , an}) as v(a1) . . . v(an), e. g., v over {p, q} with v(p) = T and v(q) = U will be written as TU. We denote the set of four-valued interpretations over At by V4(At). Notice that V2(At) V3(At) V4(At). If it is clear that an interpretation is tworespectively three-valued, we will denote it by (a possibly indexed) ω respectively ν. Two useful orders over these truth values are the information order i and the truth order t, which form the following bilattice-structure (Belnap 1977):

Notice that V4(At) also forms a bounded lattice under i with v U and v I as least and greatest element respectively (where v U is defined as the interpretation that sets v U(a) = U for every a At and v I is defined as v I(a) = I for every a At). We shall interpret the four truth values, at least for atoms, in the same way as (Belnap 2019): U (undecided) means that we have no explicit information for either the truth nor the falsity of an atom. T (true) respectively F (false) means that we have explicit information only for the truth respectively the falsity of the atom in question. Finally, I (inconsistent) means that we have explicit information for both the truth and the falsity of the atom in question. When it comes to complex formulas, we take a somewhat hybrid position between truth values expressing merely explicit information and truth values standing for objective truth. In particular, the logic we will define here will allow for logically contingent formulas, i. e., formulas which are neither classical tautologies nor classical falsities, to be assigned any of the four truth values, whereas classical tautologies and classical falsities will always be assigned T respectively F by any

interpretation. Intuitively, this means that even though the truth value of s At might be undetermined (U) or inconsistent (I), the logic will still evaluate s s as true. This is in complete agreement with ADFs, where tautologies and logical falsities are always evaluated in agreement with classical logic by i[v]2. Semantically, we proceed as follows: we construct a set of sets of (two-valued) worlds on the basis of a four-valued interpretation v that represents the beliefs expressed by v. Just like in the logic underlying ADFs i[ν]2, a set of (twovalued) worlds will be used to represent a three-valued interpretation ν. The worlds in [ν]2 represent equally plausible candidates of the actual world in view of the beliefs expressed by the three-valued interpretation ν. Likewise, a set of three-valued interpretations [v]3 will be used to represent the information expressed by a four-valued interpretation v. [v]3 consists of the three-valued interpretations that jointly represent the information expressed by v. Notice the difference with [ν]2: [ν]2 consists of equally plausible candidates of the actual world in view of the information expressed by v, whereas [v]3 contains interpretations that taken together represent the information expressed by v. We now develop this idea in more formal details. Given a four-valued interpretation, we define the set of two-valued completions of v, [v]2, in two steps. First, we construct [v]3, which converts v V4(At) to a set of three-valued interpretations [v]3 V3(At). Then, we obtain [v]2 (V2(At)) by converting every three-valued interpretation ν [v]3 to a set of two-valued interpretations [ν]2. Definition 3. Given a four-valued interpretation v V4(At), [v]3 = {ν V3(At) | for every s At : if v(s) = I then ν(s) {T, F}, ν(s) = v(s) otherwise} In other words, [v]3 is obtained by replacing every assignment of an atom s to I to an assignment of s to T or to F. Notice that [v]3 consists of the i-maximal three-valued interpretations that v extends: Fact 1. 1 For any v V4(At), [v]3 = max i({ν V3(At) | ν i v}). Example 4. Consider v = TUI over Σ = abc. Then [v]3 = {TUT, TUF}. We are now ready to define the four-valued completions [v]4 of v: Definition 4. Given some v V4(At), the four-valued completions of v are defined as: [v]4 = {[v ]2 | v [v]3}. Thus, [v]4 is obtained by first constructing [v]3, and then taking for every ν [v]3 the set of two-valued completions of ν. The intuition behind this is as follows: v(s) = I means that we have information for both s being true and s being false. Thus, the interpretations where we set ν1(s) = T and ν2(s) = F are both (partial yet consistent) representations of the state of the world represented by v. Hence [v]3 can be viewed as the set of three-valued interpretations that together form the representation of the state of the world represented by v. We then construct for every such representation a set of two-valued interpretations, which represent equally

1Due to spatial limitations, some proofs are left out.

plausible candidates of the state of the world represented by ν [v]3. Altogether, [v]4 contains a set of set of possible worlds, which together represent our knowledge about the actual state of the world. It is useful to notice that for a three-valued interpretation v V3(At), [v]4 = {[v]2}. Example 5. Consider v = TUI over Σ = {abc}. Since [v]3 = {TUT, TUF}, [TUT]2 = {TTT, TFT} and [TUF]2 = {TTF, TFF}, we see that [v]4 = {{TTT, TFT}, {TTF, TFF}}. Notice that, in order to retain the four-valued structure of an interpretation v in its four-valued completion [v]4, the two-step nature of the construction of [v]4 and the resulting nested structure of [v]4 is essential. Indeed, if [v]4 would merely consist of possible worlds, we would somehow have to choose between letting the members ω [v]4 stand as equally plausible candidates of the actual world or partial descriptions of the information given by v, i. e., we would have to choose between U and I. Conceiving of [v]4 as a set of sets of worlds avoids this choice: sets of worlds V [v]4 represent partial descriptions of the information given by v, and members of these sets of worlds ω V represent equally plausible candidates of the information in V . We can now define the assignment of truth values of complex formulas given an interpretation v based on our set of four-valued completions [v]4: Definition 5. Given a formula φ and an interpretation v, then:

T if for every Ω [v]4, iΩ (φ) = T F if for every Ω [v]4, iΩ (φ) = F I if for some Ω1 [v]4, iΩ1(φ) = T and for some Ω2 [v]4, iΩ2(φ) = F U otherwise

Thus, a complex formula φ is assigned T (respectively F) relative to an interpretation v if every four-valued completion Ω [v]4 of v, assigns T (respectively F) to φ. If there is disagreement among the four-valued completions of v on which determinate truth value φ should be assigned, v(φ) = I. Finally, if some of the four-valued completions of v do not assign any determinate truth value to φ, v(φ) = U. This way of deriving a truth value for complex formulas on the basis of a four-valued interpretation is, to the best of our knowledge, completely new. It is perfectly in line with i[v]2, the logic underlying ADFs, in the sense that for any three-valued interpretation ν V3(At) and any formula φ L, ν(φ) = i[ν]2(φ). Fact 2. For any ν V3(At) and any φ L(At), ν(φ) = i[ν]2(φ). Example 6. Consider v = TUI over Σ = abc. Observe that [v]4 = {{TTT, TFT}, {TTF, TFF}}. Thus, we have the following assignments to complex formulas: v(a c) = I, since i{TTT, TFT}(a c) = T and i{TTF, TFF}(a c) = F; v(b c) = U, since i{TTT, TFT}(b c) = U and i{TTF, TFF}(b c) = F;

v(a a) = F, since i{TTT, TFT}(a a) = F and i{TTF, TFF}(a a) = F; Remark 1. Observe that the logic 4CM, like the logic defined by i[v]2, is not truth-functional. To see this consider the interpretation v with v(a) = U and v(b) = U. Then v(a a) = T yet v(b a) = U. Thus, we see that 4CM is not truth-functional, as v(a) = v(b) = U yet v(a a) = v(b a).

5 Semantics of c ADFs In this section, we define, motivate and study the semantics of c ADFs. We first define the central ΓΠ-function and use it to define the main semantics for c ADFs. Then we motivate the design choices made in generalizing the Γ-function from ADFs to c ADFs. Finally, we show semantic properties of the semantics of c ADFs.

The ΓΠ-function and resulting c ADF-semantics A c ADF Π over At is interpreted through 4-valued interpretations. Just like for ADFs, it is of crucial importance to construct a Γ-function that allows to characterize all semantics in terms of (post-)fixpoints of this function. The Γ-function, conceptually, performs the following operation for ADFs: given an interpretation ν and an ADF D, ΓD(ν) assigns to every atom s the truth value determined by ν and Cs. In other words, ΓD(ν)(s) is the value s should take in view of the information expressed by s Cs and ν. If (for every s S), this value is compatible (in terms of i) with the actual value v(s), then v will be admissible or even complete. We generalize this idea to the case of c ADFs, and take, intuitively, ΓΠ(v) as the set of interpretations that evaluate φ in accordance with the information given by φ ψ Π and v. More formally, we define the Γ-function ΓΠ : V4(At) (V4(At)) for a c ADF Π and an interpretation v V4(At) as follows:

ΓΠ(v) = min i {v V4 | φ ψ Π : v (φ) i v(ψ)}

Example 7. Let Π = {p s ; s p} formulated over the signature Σ = {p, s}. We have the following interpretations and corresponding outcomes of the ΓΠ-function:

v ΓΠ(v) UU {UT, TU} UT {UT, TU} UF {UT, TU} UI {UT, TU} TU {TF, FI} TT {TF, FI} TF {TF, FI} TI {TF, FI}

v ΓΠ(v) FU {UT} FT {UT} FF {UT} FI {UT} IU {TI, FI} IT {TI, FI} IF {TI, FI} II {TI, FI}

We explain ΓΠ(UU) as follows: in view of p s and UU( ) = T, every interpretation v ΓΠ(UU) has to assign a truth value at least as informative as T to p s, i.e. v (p s) i T. Likewise, since UU(p) = U and s p Π, v ΓΠ(UU) has to set v ( s) i U, which is trivially the case. The two i-minimal interpretations that satisfy this constraint are: UT and TU.

As a second example, consider FF. Like with UU, every interpretation v ΓΠ(FF) has to assign v (p s) i T. However, since FF(p) = F and s p Π, any v ΓΠ(FF) has to set v ( s) i F. UT is the unique iminimal interpretation satisfying these constraints.

We first notice that ΓΠ is indeed a generalization of the ΓD-function for ADFs. To show this in a more formally precise manner, we first define the c ADF ΠD associated with an ADF D.

Definition 6. Given an ADF D = (S, L, C), we define the c ADF ΠD associated with D as ΠD = {s Cs | s S}.

We can now show that for any three-valued interpretation ν, ΓΠD(ν) coincides with ΓD(ν), i.e. the Γ-function for ADFs coincides with the Γ-function for the associated c ADFs for three-valued interpretations.

Proposition 1. For any ADF D = (S, L, C) and any ν V3(S), ΓΠD(ν) = {ΓD(ν)}.

The above result shows that the ΓΠ-function is a direct generalization of the well-studied ΓD-function known from ADFs. This allows us to define the main semantics of c ADFs in terms of (post-)fixpoints of the ΓΠ-functions, just like in the case of ADFs. With our generalized ΓΠ-function at hand, we can now define the main semantics for c ADFs as straightforward generalizations of the ADF-semantics:

Definition 7. Let a c ADF Π over At and an interpretation v V4(At) be given, then:

v is admissible for Π iff there is some v ΓΠ(v) s.t. v i v . v is complete for Π iff v ΓΠ(v). v is preferred for Π if it is a i-maximal among all admissible interpretation for Π; v is grounded for Π if it is a i-minimal among all complete interpretation for Π; v is a two-valued model for Π iff v V2(At) and v is complete.

Example 8 (Example 7 ctd.). We see that for Π from Example 7, there are two complete interpretations: TF and UT. This can be seen by observing that TF ΓΠ(TF) and UT ΓΠ(UT). Since these interpretations are iincomparable, both interpretations are also grounded. The admissible interpretations are: UU, UT, TU and TF. Thus, UT and TF are also preferred.

Example 9. Let Π = {b p, f b, f p} formulated over Σ = {b, f, p} be given. v U = UUU is the unique complete interpretation and thus also grounded. It is also the unique admissible interpretation. Notice that e.g. TIT is not complete, since ΓΠ(TIT) = {TIU}. The reason for ΓΠ(TIT)(p) = U is since there is no acceptance pair p φ Π. The intuition is that p is only accepted if we have good information to do so, but no such information is given by any φ ψ Π. It is interesting to note that for Π = Π {p p}, TIT ΓΠ (TIT) = {TIU, TIT, TIF}.

As can be seen in the example above, if an atom a occurs in no statement of φ of any acceptance pair φ ψ Π, then v(a) = U for any admissible or complete interpretation v. However, should this be undesired, one can simply add the acceptance pair a a for such an atom.

Design Choices in ΓΠ and Comparison with ΓD We now discuss the design choices made in generalizing the Γ-function from ADFs to c ADFs. A first generalization is caused by the fact that statements φ of acceptance pairs φ ψ are possibly non-atomic formulas. Since ΓΠ contains all interpretations v that align, for any φ ψ Π, the truth value of φ with v(ψ), there might now be more than one interpretation v which achieves this. As a case in point, consider the c ADF Π = {p q }, where acceptance of p q (which is required by any v V4, since v( ) = T for any v V4) can be guaranteed by any interpretation that satisfies p or q. Therefore, the Γfunction might contain multiple interpretations which all do an equally good job of aligning the truth values of statements φ with their respective conditions ψ. Thus, ΓΠ is defined as a non-deterministic operator (Pelov and Truszczynski 2004; Heyninck and Arieli 2021), in the sense that a single interpretation v might give rise to a non-singleton set of interpretations {v1, . . . , vn} = ΓΠ(v). In the example above, we have e.g. ΓΠ(v) = {TU, UT} for any v V4({p, q}). A second generalization w.r.t. the Γ-function for ADFs is the fact that alignment of statements φ with their corresponding condition ψ cannot always be done in an exact way. In more detail, for ADFs D, alignment by ΓD of s is always exact, in the sense that ΓD(v)(s) coincides with the truth value assigned by i[v]2(Cs). This is not always possible for c ADFs, since we might have conflicting specifications in a c ADF. Take for example the c ADF Π = {p ; p }. Clearly, for any v V4(At), there exists no v V4(At) s.t. v (φ) = v(ψ) for every φ ψ. Indeed, this is one of the reasons we had to move to a fourvalued logic, since now we can at least specify an interpretation v which brings v (p) and v ( p) in alignment with v( ), in the sense that v (p) and v ( p) are at least as informative as v( ), i.e. v (p) i v( ) and v ( p) i v( ) (for any v V4(At)).

Semantical Properties of c ADF-semantics In this section, we show central semantical results on the semantics of c ADFs. In particular, we show some relationships between the semantics, and we show under which conditions admissible, complete, grounded and preferred interpretations are guaranteed to exist. We start by observing that, just like for ADFs, complete interpretations are admissible:

Proposition 2. Let a c ADF Π and a complete interpretation v for Π be given. Then v is admissible.

For showing the existence of all semantics, it will be useful to limit attention to what we will call well-formed c ADFs. The main idea is that we want to avoid c ADFs Π for which ΓΠ(v) = for some v V4(At), as occurs in e.g. the following example:

Example 10. Π = {p , p , p p p}.

v ΓΠ(v) v ΓΠ(v) T {I} F {I} U {I} I

Notice that Γ(I) = .

Definition 8. A well-formed c ADF is a c ADF Π s.t. ΓΠ(v) = for any v V4(At).

As a side note, we observe that a syntactic sufficient condition for well-formedness of a c ADF Π is to simply require that for every acceptance pair φ ψ Π, the statement φ is a logically contingent formula. We call such c ADFs unconstrained:

Definition 9. A c ADF Π is unconstrained iff for every φ ψ Π, φ is logically contingent.

We explain the term of unconstrained c ADF as follows. Notice that an acceptance pair φ ψ, where φ is a tautology or a falsity, can be seen as a constraint, in the sense that it forces ψ to be set to the value of φ (i.e. v(ψ) = T if ψ is a tautology and v(ψ) = F if ψ is a falsity) for any complete extension. To see this, observe that v(φ) = T[F] for any v V4 if φ is a tautology[falsity]. In particular, for any v ΓΠ(v), it will hold that v(φ) = T[F]. It is quite interesting that the framework naturally allows for the formulation of constraints, but for the development of the meta-theory, it will prove useful to restrict attention to well-formed c ADFs. It is an interesting question for future work to see whether constrained argumentation frameworks (Coste-Marquis, Devred, and Marquis 2006) can be captured using such constraints.

Proposition 3. Any unconstrained c ADF Π is well-formed.

However, not all well-formed c ADFs are unconstrained:

Example 11. Consider Π = {a a a a}. Then clearly, for any v V4(At), ΓΠ(v) = {T} (since [U]2 = {T, F} and i{T, F}(a a) = T).

All semantics exist for well-formed c ADFs:

Proposition 4. For any well-formed c ADF, there exists an admissible, preferred, complete and grounded interpretation.

6 Grounded Interpretations and the Grounded State One of the crucial properties of ADFs is that a unique grounded interpretation is guaranteed to exist. This property does not generalize to the grounded semantics of c ADFs, in view of the indeterminism that c ADFs allow to express. As a case in point consider Π = {p q }, which has two i-minimal complete interpretations: v1 and v2 with: v1(p) = T, v1(q) = U, v2(p) = U and v2(q) = T. Thus, there might be c ADFs that do not have a unique grounded interpretation. This might be seen as problematic, since the grounded interpretation for ADFs can be calculated efficiently and straightforwardly by iterating ΓD starting from v U. Since the grounded interpretation vg is i-minimally complete and unique for ADFs, it approximates any other complete interpretation of the ADF in question (in the sense

that vg i v for any complete interpretation v). We are now interested in defining a similar concept for c ADFs, that is, a unique representation of the i-minimal information expressed by a c ADF that can be unambigously obtained by application of ΓΠ and approximates any complete interpretation. This can be done by looking at a set of interpretations instead of a single interpretation. We note that this idea is not new. For example, many well-founded semantics for disjunctive logic programming take up this idea, resulting in a well-founded state (Baral, Lobo, and Minker 1992; Brass and Dix 1995; Alcˆantara, Dam asio, and Pereira 2005).2 Accordingly, we will be interested in a grounded state V V4(At) that represents the minimal knowledge entailed by a c ADF. This grounded state can be defined as the S i -minimal fixpoint of Γ Π, a generalization of ΓΠ to sets of interpretations. Γ Π is obtained as follows: Definition 10. Given a c ADF Π and V V4(At):

Γ Π(V ) = min i

We lift i to sets of interpretations by defining, for V1, V2 V4(At), V1 S i V2 iff for every v2 V2 there is some v1 V1 s.t. v1 i v2. Definition 11. Let a c ADF Π be given. V V4(At) is: (1) a complete state (for Π) iff V = Γ Π(V ), (2) a grounded state (for Π) iff V is a S i -minimally complete state (for Π). Proposition 5. Let a c ADF Π be given. Then: 1. There exists a unique grounded state which can be obtained by iterating Γ Π, starting with v U. 2. For any ADF D, the grounded state coincides with {v}, where v is the grounded interpretation of D. 3. Where V is the grounded state for Π and v is a complete interpretation of Π, we have that: V S i {v}. Example 12. Let Π = {p q , s p, s q} over the signature {p, q, s}. Then we can obtain the grounded state for Π by the following calculation: (1) Γ Π({v U}) = {TUU, UTU}; (2) Γ Π(Γ Π(v U)) = min i(ΓΠ(TUU) ΓΠ(UTU)) = {TUT, UTT}; (3) Γ Π(Γ Π(Γ Π(v U))) = min i(ΓΠ(TUT) ΓΠ(UTT)) = {TUT, UTT}. Since in the third step a fixed point was reached, we see that the grounded state of Π is {TUT, UTT}. The grounded state consists of two interpretations, which both make s true, and either make p or q true. Remark 2. All semantics defined in this paper have been implemented in Java using the Tweety-library (Thimm 2017).

7 Related Work To the best of our knowledge, no generalizations of ADFs as we have suggested here have been proposed before. As a

2Some semantics explicitly use the idea of a set of interpretations (Alcˆantara, Dam asio, and Pereira 2005), whereas other semantics are phrased syntactically, as a a set of disjunctions (Baral, Lobo, and Minker 1992; Brass and Dix 1995), which is equivalent to a set of interpretations (Seipel, Minker, and Ruiz 1997).

side effect of the semantics of c ADFs, we obtain also a fourvalued semantics of ADFs and argumentation frameworks. However, epistemic graphs (Hunter, Polberg, and Thimm 2020) can be regarded as an orthogonal approach to extend the expressivity of ADFs. There, general propositional formulas are interpreted through a probabilistic semantics (that is not related to ADF semantics), thus yielding an expressive probabilistic and argumentative formalism. Instead, we have a purely qualitative formalism that generalises the original ADF semantics directly. Attacks on sets of arguments are possible in SETAFs (Nielsen and Parsons 2006). However, in SETAFs, only attacks from sets of arguments are allowed, and not on sets of arguments. Furthermore, support is not studied in SETAFs. In future work, we will study how to formulate c ADFs that model attack and support between sets of arguments. Four-valued semantics for the more specific abstract argumentation frameworks have been proposed in (Baroni, Giacomin, and Liao 2015; Arieli 2012). The semantics of 4CM bears similarities to those of generalized possibilistic logic (in short, GPL) (Dubois 2012), where a pair of sets of possible worlds is used to represent the information given by a four-valued interpretation. [v]4 might consist of more than two sets of worlds, which results in e.g. v I(p) = v I(q) = v I( p q) = I, different form GPL. ADFs have been generalized in other works, in particular as to allow for the handling of weights (Brewka et al. 2018; Bogaerts 2019). In (Brewka et al. 2018) an instantiation of weighted ADFs using Belnap s four-valued logic is discussed. However, in the setting of (Brewka et al. 2018) this results in five truth-values, since in weighted ADFs, the truth-values are always supplemented with an informationtheoretic minimum U that is not part of the original set of truth-values. This is counter-intuitive, as Belnap s truthvalues already include a truth-value expressing undecidedness. Furthermore, this instantiation uses Belnap s fourvalued logic to evaluate complex formulas, which means that tautologies can be both assigned Belnap s inconsistent and incomplete truth-values (but never the external U-value). Finally, syntactically, weighted ADFs conform with ADFs in the sense that they require exactly one acceptance condition to be assigned to every node, and thus, the syntax of c ADFs also generalizes the syntax of weighted ADFs.

8 Conclusion In this paper, we have defined and studied c ADFs, which generalize ADFs and allow for indeterminism, overand underspecifications. Semantics for c ADFs are defined in terms of a Γ-function mapping four-valued interpretations to sets of four-valued interpretations. There remains still a lot of work to be done on c ADFs. As a first next step, there are still some semantics that need to be generalized from ADFs to c ADFs, in particular the stable semantics. Thereafter, we plan to study the computational complexity and realizability (in the style of (P uhrer 2020)) of c ADFs. On the basis of these steps, we will then have a clear view of which formalisms can be captured by c ADFs, e.g. disjunctive and propositional logic programming (Minker and Seipel 2002; Ferraris 2005) and logics for nonmonotonic conditionals (Kraus, Lehmann, and Magidor 1990).

Acknowledgements The research reported here was supported by the Deutsche Forschungsgemeinschaft under grant KE 1413/11-1.

References Alcˆantara, J.; Dam asio, C. V.; and Pereira, L. M. 2005. A well-founded semantics with disjunction. In International Conference on Logic Programming, 341 355. Springer. Arieli, O. 2012. Conflict-tolerant semantics for argumentation frameworks. In European Workshop on Logics in Artificial Intelligence, 28 40. Springer. Baral, C.; Lobo, J.; and Minker, J. 1992. Generalized disjunctive well-founded semantics for logic programs. Annals of Mathematics and Artificial Intelligence, 5(2): 89 131. Baroni, P.; Giacomin, M.; and Liao, B. 2015. I don t care, I don t know. . . I know too much! On Incompleteness and Undecidedness in Abstract Argumentation. In Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation, 265 280. Springer. Belnap, N. D. 1977. A useful four-valued logic. In Modern uses of multiple-valued logic, 5 37. Springer. Belnap, N. D. 2019. How a computer should think. In New Essays on Belnap-Dunn Logic, 35 53. Springer. Bogaerts, B. 2019. Weighted abstract dialectical frameworks through the lens of approximation fixpoint theory. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 2686 2693. Brass, S.; and Dix, J. 1995. Disjunctive Semantics based upon Partial and Bottom-Up Evaluation. In ICLP, 199 213. Brewka, G.; Strass, H.; Ellmauthaler, S.; Wallner, J. P.; and Woltran, S. 2013. Abstract dialectical frameworks revisited. In ICJAI. Brewka, G.; Strass, H.; Wallner, J. P.; and Woltran, S. 2018. Weighted abstract dialectical frameworks. In Thirty-Second AAAI Conference on Artificial Intelligence. Cayrol, C.; and Lagasquie-Schiex, M.-C. 2005. On the acceptability of arguments in bipolar argumentation frameworks. In European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, 378 389. Springer. Coste-Marquis, S.; Devred, C.; and Marquis, P. 2006. Constrained Argumentation Frameworks. KR, 6: 112 122. Dubois, D. 2012. Reasoning about ignorance and contradiction: many-valued logics versus epistemic logic. Soft Computing, 16(11): 1817 1831. Dung, P. M. 1995. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. AI, 77: 321 358. Ferraris, P. 2005. Answer sets for propositional theories. In International Conference on Logic Programming and Nonmonotonic Reasoning, 119 131. Springer. Heyninck, J.; and Arieli, O. 2021. Approximation Fixpoint Theory for Non-Deterministic Operators and Its Application in Disjunctive Logic Programming. In accepted for the International Conference on Principles of Knowledge Representation and Reasoning.

Heyninck, J.; Kern-Isberner, G.; Skiba, K.; and Thimm, M. 2019. Interpreting Conditionals in Argumentative Environments. In NMR 2020 Workshop Notes, 73. Hunter, A.; Polberg, S.; and Thimm, M. 2020. Epistemic Graphs for Representing and Reasoning with Positive and Negative Influences of Arguments. Artificial Intelligence, 281: 103236. Kraus, S.; Lehmann, D.; and Magidor, M. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. AI, 44(1-2): 167 207. Minker, J.; and Seipel, D. 2002. Disjunctive logic programming: A survey and assessment. In Computational logic: logic programming and beyond, 472 511. Springer. Nielsen, S. H.; and Parsons, S. 2006. A generalization of Dung s abstract framework for argumentation: Arguing with sets of attacking arguments. In International Workshop on Argumentation in Multi-Agent Systems, 54 73. Springer. Pelov, N.; and Truszczynski, M. 2004. Semantics of disjunctive programs with monotone aggregates: an operator-based approach. In Proceedings of NMR 04, 327 334. Polberg, S. 2016. Understanding the abstract dialectical framework. In European Conference on Logics in Artificial Intelligence, 430 446. Springer. P uhrer, J. 2020. Realizability of three-valued semantics for abstract dialectical frameworks. Artificial Intelligence, 278: 103198. Seipel, D.; Minker, J.; and Ruiz, C. 1997. Model generation and state generation for disjunctive logic programs. The Journal of Logic Programming, 32(1): 49 69. Thimm, M. 2017. The Tweety library collection for logical aspects of artificial intelligence and knowledge representation. KI-K unstliche Intelligenz, 31(1): 93 97.