Investigating subclasses of abstract dialectical frameworks

2.1.Abstract argumentation frameworks

Let F=(A,R) be an AF. When used for modelling purposes it is usually assumed that the set of arguments A is finite. Also, for each a,b∈A, the relation (a,b)∈R is used to represent that a is an argument attacking the argument b. We can then also say that an argument b∈A is attacked by a set S⊆A if there is a a∈S that attacks b. An argument a∈A is, on the other hand, defended by a set S⊆A of arguments (alternatively, the argument is acceptable with respect to S) (in F) if for each argument c∈A, it holds that if (c,a)∈R then there is a s∈S such that (s,c)∈R. In addition, a subset S of A is called conflict-free in F, if it does not attack itself. I.e. there are no a,b∈S such that (a,b)∈R.

In abstract argumentation, diverse criteria that have been formulated for conflict-resolution are encoded into so called semantics. In the case of AFs, semantics identifiy sets of arguments which it is reasonable to accept together (w.r.t. the semantics at hand). One standard way of defining the semantics for a given AF F=(A,R) is via the so called characteristic operator ΓF: a function mapping a set of arguments of F to the set of arguments defended by itself. Formally, let S be a subset of A, then ΓF(S)={a∈A|a is defended by S in F}. We compile the definitions of some of the main semantics of AFs given in terms of the characteristic operator in the following:

We recall that, for each AF, the grounded set is the unique subset-minimal complete set. Moreover, for a given AF a stable model might not exist, while the remaining semantics produce at least one set of arguments for any AF. Note also that we use the notion of a “stable model” rather than “stable extension” simpliciter (as is more common for AFs) just for using terminology compatible with that used for the semantics of ADFs (where stable models are a subclass of two-valued-models) which we introduce later-on in Definition 6.

We now turn to the generalization of AFs introduced by Nielson and Parsons, in which the attack relation is generalised to also include attacks from sets of two or more arguments [27].

Given a SETAF (A,R), we write S↦Rb if there is a set S′⊆S attacking b, i.e. (S′,b)∈R. We say that in this case also S attacks b. Moreover, we write S′↦RS if S′↦Rb for some b∈S. We drop the subscript in ↦R if the attack relation is clear from the context.

Notions of conflict and defense can be defined for SETAFs in analogy to these notions in the context of AFs. Given a SETAF F=(A,R), a set S⊆A is conflicting in F if S↦RS; S⊆A is conflict-free in F, if S is not conflicting in F, i.e. if S′∪{a}⊈S for each (S′,a)∈R. An argument a∈A is defended (in F) by a set S⊆A if for each B⊆A, such that B↦Ra, also S↦RB. A set T of arguments is hence defended (in F) by S if each a∈T is defended by S (in F).

The semantics of SETAFs can now also be defined similarly to AFs via a characteristic operator. With a slight abuse of notation (because of the use of the same notation for the characteristic operator), we thus define first of all also for a SETAF F=(A,R), ΓF(S)={a∈A|a is defended by S in F}; here the notion of “defense” clearly being that defined for SETAFs. For completeness we detail the definitions of all semantics we consider in this work for SETAFs, although the definitions are exactly as those for AFs (modulo the use of the more general notions of attack and that the characteristic operator referenced therein is the characteristic operator defined for SETAFs):

We will use the same abbreviations for SETAFs as for AFs for denoting the sets of arguments obtained when applying the semantics on SETAFs. We also recall that several important properties of Dung AFs carry over to SETAFs; we refer to [21,27] for details.

In the following we provide an example of a SETAF and also illustrate the concept of extensions and semantics for SETAFs.

Example 1.

The SETAF F=({a,b,c},{({a,b},c),({a,c},b)}) is depicted in Fig. 1. In F, ({a,b},c)∈R says that there is a joint attack from a and b to c, and ({a,c},b)∈R says that there is a joint attack from a and c to b. The former attack represents that neither a nor b are strong enough to attack c by themselves. The latter attack indicates that neither a nor c are strong enough to attack b by themselves. The conflict-free extensions of F are cf(F)={{},{a},{b},{c},{a,b},{a,c},{b,c}}, the admissible extensions adm(F)={{},{a},{a,b},{a,c}}, the complete extensions com(F)={{a},{a,b},{a,c}}, the unique grounded extension grd(F)={{a}}, and the preferred extensions prf(F)=stb(F)={{a,b},{a,c}}. Note that, for instance, {b,c} is a conflict-free extension. However, it is not an admissible extension, since {b,c}⊈(ΓF({b,c})={}). Further, {a} is an admissible and a complete extension, since ΓF({a})={a}. On the other hand {a} is not a preferred extension because it is not a ⊆-maximal admissible extension.

Fig. 1.

The SETAF of example 1.

2.2.Abstract dialectical frameworks

We now proceed to define ADFs:

Graphically, ADFs can be depicted as annotated directed graphs where nodes represent arguments, directed edges represent links (tuples of nodes). Acceptance conditions are shown via annotations next to the nodes representing the arguments. See Fig. 2 for an example of the depiction of an ADF (we present later on in Example 2).

Semantics of ADFs are defined in terms of interpretations. Concretely, let D=(S,L,C) be an ADF. An interpretation v (for D) is then a function mapping each of the arguments in S to one of the truth values true (t), false (f), or undecided (u), i.e. v:S↦{t,f,u}. The truth values stand for different degrees of acceptance that can be associated to the arguments. The sets vt, vf, and vu contain those arguments that v maps to true, false and undecided, respectively. An interpretation v is two-valued if it maps each argument to either t or f, i.e. vu=∅. At the other extreme, an interpretation v is called trivial, denoted vu, if v(s)=u for each s∈S. Also, we denote the update of an interpretation v with a truth value x∈{t} for an argument b by v|xb, i.e. v|xb(b)=x and v|xb(a)=v(a) for a≠b.

Let V be the set of all interpretations for an ADF D as before. Then, we call a subset of all interpretations of the ADF, V⊆2V, an interpretation-set. Interpretations can now be ordered with respect to their information content. This is based on the partial order of truth values, for which u⩽it and u⩽if. An interpretation v is at least as informative as another interpretation w, denoted by w⩽iv, if w(s)⩽iv(s) for each s∈S. As usual w<iv whenever w⩽iv but it is not the case that v⩽iw. The meet operator ⊓i on truth values is defined as t⊓it=t, f⊓if=f and returns u otherwise. The meet ⊓i of two interpretations v and w is then defined as (v⊓iw)(s)=v(s)⊓iw(s) for each s∈S. The partially ordered set ({t,f,u},⩽i) forms a meet-semilattice with the meet operator ⊓i.

Semantics for ADFs can also be defined via a characteristic operator ΓD for an ADF D, although given that the semantics of ADFs give interpretations rather than sets of arguments, the definitions now deviate somewhat to that for AFs and SETAFs. Given an interpretation v (for D), the characteristic operator ΓD for D is defined as

The semantics for ADFs, as defined via the characteristic operator, are provided next in Definition 6. The definitions have been introduced in [4,8]; we refer to [6] for an in-depth overview of the semantics of ADFs in terms of approximation fixpoint theory and the connections to the definitions of the semantics for AFs (and SETAFs).

In ADFs links between arguments or statements can be classified into four types, reflecting the relationship of attack and/or support that exists between the statements. These are listed in the following definition.

The classification of the types of the links of ADFs is also relevant for classifying ADFs themselves. Thus, one particularly important subclass of ADFs is that of bipolar ADFs or BADFs for short, first defined in [8]. In such an ADF each link is either attacking or supporting (or both; thus, the links can also be redundant). The following example clarifies the role of the acceptance conditions in ADFs and illustrates the functioning of the different semantics in the context of ADFs.

Example 2.

An example of an ADF D=(S,L,C) is shown in Fig. 2. To each argument a propositional formula is associated, the acceptance condition of the argument. In the acceptance condition of an argument only the parents of that argument occur as variables. The acceptance condition indicates how the acceptance-status of an argument depends on that of its parents in the ADF. For instance, the acceptance condition of c, namely φc:¬a∨¬b, states that c can be accepted in an interpretation where either a or b (or both) are rejected. The acceptance condition φa:⊥ states that a always has to be rejected. The acceptance condition φb:a∨b∨¬c indicates that b can be accepted if and only if a or b is accepted or c is rejected, thus also indicating a form of self-support for b.

Fig. 2.

The ADF of example 2.

Since in ADFs an argument appears in the acceptance condition of an argument a if and only if it belongs to the set par(a), the set of links L of an ADF is given implicitly via the acceptance conditions. Thus we often also don’t give an explicit representation of the links in the examples we provide in this work. For instance, since b appears in φb, (b,b)∈L. Moreover, given that for every two-valued interpretation v, v(φb)=t implies v|tb(φb)=t, the link (b,b) is supporting (in D). Further, D is a bipolar ADF in which L+={(a,b),(b,b)} is the set of all supporting links, and L−={(a,c),(b,c),(c,b)} is the set of all attacking links.

In D the interpretation v={a↦u,b↦u,c↦t} is conflict-free. However, v is not an admissible interpretation, because ΓD(v)={a↦u,b↦u,c↦u}, that is, v≰iΓD(v). The interpretation v1={a↦f,b↦u,c↦u} on the other hand is an admissible interpretation and, in fact, also the unique grounded interpretation of D. Further, prf(D)=mod(D)={{a↦f,b↦f,c↦t},{a↦f,b↦t,c↦t}}, but only the first interpretation in this set is a stable model. This is because for v={a↦f,b↦f,c↦t} the unique grounded interpretation w of Dv is {c↦t} and vt=wt. The interpretation v′={a↦f,b↦t,c↦t} is not a stable model, since the unique grounded interpretation w′ of Dv′ is {b↦u,c↦t} and v′t≠w′t. In addition, we have that for the ADF D, com(D)=prf(D)∪grd(D).

As to the relationship between ADFs and AFs, an ADF D=(S,L,C) is AF-like if the acceptance condition of every argument s∈S is of the form φs=⋀a∈par(s)¬a (by the usual conventions, we thus have that if par(s)=∅, then φs=⊤). Such an ADF can be represented as an AF, as a tuple F=(A,R) with arguments A=S and attacks R=L. In turn, each AF can be represented as an ADF via the following definition.

It is shown in [4,8] that the semantics of AFs and associated ADFs coincide. Also note that the associated ADF DF of each AF F is a BADF in which all links are attacking. In fact, BADFs are a strict superclass of AFs and strict subclass of ADFs.

An ADF D=(S,L,C) is, on the other hand, SETAF-like if the acceptance condition of every argument s∈S is given by a formula where each occurrence of an atom has negative polarity and is different to ⊥. The reason behind this definition is the fact that in [36] it is shown that an ADF can directly be written as a SETAF if the acceptance condition of each argument is in conjunctive normal form and consists only of negative literals (note that arbitrary formulas where each atom occurs only having negative polarity can be transformed to such a CNF). We come back to this issue later in Section 3.3 where we introduce a further subclass of ADFs, support-free ADFs, that contains the class of SETAFs.

To conclude the preliminaries to our work we note that, just as AFs, also SETAFs can be represented as ADFs. This is captured in the following definition.

3.1.Acyclic ADFs

In this section we show that, as has already been indicated and is the case for acyclic AFs, also for acyclic ADFs several semantics coincide (Theorem 2). We start by defining acyclic ADFs.

In order to prove that the different semantics coincide on acyclic ADFs we need the concepts of level and maximum level of arguments. The level of an argument s of an ADF D is the number of links on the longest path from an initial argument to s plus 1. The maximum level of an (acyclic) ADF D then is the level of an argument of D that is at least as large as the level of any other argument of D. It is clear that every acyclic ADF has a maximum level. This is a crucial observation needed for our proof of Proposition 1, which in turn provides the basis to show that most semantics defined for ADFs are indistinguishable when evaluating acyclic ADFs.

An immediate consequence of Theorem 2 is that any acyclic ADF D possesses a non-trivial preferred interpretation, which is also a complete interpretation, grounded interpretation, stable interpretation, and a model. We conclude by noting that, on the other hand, if all semantics of an ADF coincide, there is no guarantee that the ADF in question is acyclic. This is shown via Example 3.

The ADF of Example 3 in fact represents an AF. Therefore, there is also no guarantee that an AF is acyclic, whenever all semantics yield the same extensions.

3.2.Symmetric ADFs

We turn now to our study of symmetric ADFs. We consider the properties of coherence (stable and preferred semantics coincide) and relatively-groundedness (grounded extension is the intersection of all preferred extensions) which have been shown to hold for symmetric AFs [10]. Since both the two-valued and stable model semantics for ADFs are proper generalisations of the stable semantics for AFs [4], we consider further forms of coherence (weak coherence and semi-coherence; defined in Definition 12) that are possible in the realm of ADFs.

We will show that, contrary to symmetric AFs, symmetric ADFs do not satisfy any of the forms of coherence for ADFs we define, nor are they relatively-grounded (Theorem 3). We then define a further restricted form of symmetric ADFs, acyclic support symmetric ADFs, or ASSADFs for short (Definition 14), which we show do satisfy a weak form of coherence (each two-valued model is a stable model) (Theorem 5). Nevertheless, we conclude (Theorem 6) by showing that in ASSADFs it is still not the case that every preferred interpretation is a two-valued-model (semi-coherence). We also show that ASSADFs are not relatively-grounded (again, Theorem 6).

We start by giving the definition of symmetric ADFs.

The reason why we have to exclude redundant links is that otherwise we are able to add arbitrary links without changing the semantics of the ADF at hand: informally speaking, given an ADF D=(S,L,C), take any link (a,b)∈L such that (b,a)∉L and do the following: add (b,a) to L and change the acceptance condition φa to φa∧(¬b∨b). From the definition of the semantics, it follows that such a modification cannot change the set of σ-interpretations of ADF. Now, applying this modification exhaustively turns L into a symmetric relation. The added links are clearly redundant since the newly introduced parent has no semantic effect on the altered acceptance condition.

Next we provide several notions of coherence which are possible for ADFs.

We now turn to define the notion of relatively-groundedness for ADFs.

In what follows, we occasionally say that a class C of ADFs is coherent (resp. semi-coherent, weakly coherent, relatively grounded) if each of its elements satisfies the respective property.

It turns out that neither of the properties analogous to those holding for symmetric AFs hold for symmetric ADFs.

Fig. 3.

A symmetric ADF which is neither semi-coherent, weakly coherent nor relatively grounded.

Note that the ADF D used as counter-example in the proof of Theorem 3 (Fig. 3), is actually a symmetric BADF since D is a symmetric ADF in which there are no dependent links and all links are either attacking or supporting. This raises the question whether there is a particular subclass of symmetric BADFs which fulfills the properties considered in Theorem 3. One natural candidate is that of acyclic support symmetric ADFs, which we present in Definition 14. For the latter we first need to define the notion of a support cycle.

The method of determining whether a given ADF is an ASSADF is clarified in Example 4.

Example 4.

Let D=(S,L,C) be the symmetric BADF depicted in Fig. 3. Since (S,L+) as shown in Fig. 4 contains a cycle, namely the sequence [d,c,d], D is not an ASSADF.

Fig. 4.

The support-links of the ADF D from Theorem 3 (Figure 3).

We now show that ASSADFs are weakly coherent, using the following technical lemma.

We conclude this section by showing, on the other hand, that there are ASSADFs which are neither semi-coherent nor relatively grounded.

Proof.

Consider the ASSADF D depicted in Fig. 5. D has 4 preferred interpretations, namely v1={a↦f,b↦f,c↦t,d↦t,e↦f}, v2={a↦f,b↦t,c↦f,d↦t,e↦f}, v3={a↦t,b↦f,c↦f,d↦t,e↦f}, and v4={a↦u,b↦u,c↦u,d↦f,e↦t}. As every two-valued interpretation of D (that is v1, v2 and v3) is also a stable model, D is weakly coherent, confirming Theorem 5. However, v4 is a preferred interpretation which is not a two-valued model. Hence, D is not semi-coherent.

Fig. 5.

An ASSADF without supporting links that is not semi-coherent.

We show now that ASSADFs are not relatively grounded in general. Consider the ASSADF D=(S,L,C), depicted in Fig. 6. Here D=({a,b,c},{φa:¬b∧¬c,φb:¬a∧¬c, and φc:a∨¬b}). D has the preferred interpretations v1={a↦f,b↦f,c↦t} and v2={a↦f,b↦t,c↦f}. We obtain v1⊓iv2={a↦f,b↦u,c↦u}. However, the grounded interpretation of D is the trivial interpretation vu. That is, D is not relatively grounded. □

3.3.Implications for SETAFs

The ASSADF used in the proof of Theorem 6 to show that ASSADFs are not semi-coherent does not have any supporting links. That is, even ASSADFs without supporting links are not semi-coherent. This leads us, in this section, to consider whether ASSADFs having only attacking links, which we call support free symmetric ADFs or SFSADFs for short (Definition 15), satisfy the other properties considered in Section 3.2: being weakly coherent and relatively grounded. We show that SFSADFs are weakly coherent, but neither semi-coherent nor relatively grounded in Theorem 8.

Fig. 6.

An ASSADF which is not relatively grounded.

Moreover, we derive from Theorem 8 that symmetric SETAFs are neither coherent nor relatively grounded (Theorem 17). The reason is that the SFSADFs we have used in the proof of Theorem 8 correspond to SETAFs. More concretely, the SETAFs in question correspond to a specific class of SFSADFs: those in which the acceptance condition of none of the arguments is unsatisfiable. On the way of proving Theorem 17 we show that, in fact, such SFSADFs exactly correspond to symmetric SETAFs (Theorem 9, Corollary 10, and Theorem 12; Lemmas 13 and 14). Thus, we obtain as a consequence of our investigations of semantic properties in the general settings of ADFs, results that complement those of [27] for SETAFS, where the authors show that the standard semantics are indistinguishable on acyclic SETAFs (a result that is confirmed by our study in Section 3.1).

We start by defining SFSADFs:

Note that since SFSADFs are BADFs by Definition 15, this means that SFSADFs do not have dependent links. Also, SFSADFs are symmetric by the same definition, which means that they do not have redundant links. Further, since SFSADFs do not have supporting links, they also do not have a support cycle. Thus, the class of SFSADFs is indeed a strict subclass of ASSADFs.

We next show that also SFSADFs, while being weakly coherent, are neither semi-coherent nor relatively grounded. Before doing so, we report a simple observation concerning the grounded interpretation.

Fig. 7.

A SFSADF that is not relatively grounded.

It is relatively easy to see that the ADFs used to show that SFSADFs are neither semi-coherent nor relatively grounded in the proof of Theorem 8 (ADFs from Figs 5 and 7) correspond to SETAFs (see Definitions 3 and 9). In fact, we proceed to show now that symmetric SETAFs are captured exactly by a subclass of SFSADFs: those in which the acceptance condition of none of the arguments is unsatisfiable. As already hinted at, apart from showing the link between SETAFs and SFSADFs this will allow us to also formally translate the content of Theorem 8 to the context of SETAFs.

We start by defining symmetric SETAFs.

In Definition 16, the first item indicates that in the associated graph of the symmetric SETAFs all links are symmetric. The second item further means that there are also no reflexive links. Finally, the third item excludes redundant links.

From Definition 9 it follows that each SETAF can be represented as an ADF. Thus, also symmetric SETAFs can be encoded as ADFs. We now show that in fact symmetric SETAFs correspond to SFSADFs.

Let F=(A,R) be a SETAF and let a be an argument on which there is no attack in F, that is, there is no (B,a)∈R. By Definition 9, in the ADF corresponding to the SETAF F the acceptance condition of a has the form φa=⋀(B,a)∈R⋁a′∈B¬a′≡⊤. On the other hand, if there exists (B,a)∈R, it holds that φa=⋀(B,a)∈R⋁a′∈B¬a′≢⊥. These facts together with Theorem 9 lead to the following corollary.

Next, we detail how the special group of SFSADFs that do not have any argument with an unsatisfiable acceptance condition can be represented as SETAFs. For this we make use of a fact from [36], namely that ADFs for which the acceptance condition of each argument is either tautological or in CNF having only negative literals can be represented as SETAFs. Note that in symmetric ADFs each initial argument needs to be isolated and thus might have acceptance condition ⊤ or ⊥; the latter is problematic in representing SFSADFs as symmetric AFs and thus needs special treatment.

We now provide the construction associating a SETAF to every SFSADF for which no argument has an unsatisfiable acceptance condition.

Analogously to Theorem 9, we show in Theorem 12 that SFSADFs in which none of the acceptance conditions of the arguments is unsatisfiable can be mapped to symmetric SETAFs.

The SFSADF D=({a,b,c,d},{φa=¬b∧¬c,φb=¬a∧¬c∧¬d,φc=¬a∧¬b∧¬d,φd=¬b∨¬c}), depicted in Fig. 7, corresponds to the symmetric SETAF FD=({a,b,c,d},R) with R={({a},b),({b},a),({a},c),({c},a),({b},c),({c},b),({b,c},d),({d},b),({d},c)}) depicted in Fig. 8. As can be seen in the figure, in this SETAF there is a joint attack from b and c to d. This joint attack is symmetric in the sense of Definition 16, because of ({d},b)∈R and ({d},c)∈R.

Fig. 8.

A symmetric SETAF that is not relatively grounded.

Now, in order to be able to relate SFSADFs and symmetric SETAFs on the semantic level, we first make precise the relation between extension-based semantics of AFs and interpretation-based semantics of ADFs. To do so, we start by introducing some terminology. Given a formalism F, the set of all extensions of F are denoted by E and the set of all possible interpretations of F are denoted by V. The function Ext2IntF, in Definition 18, is a modification of the function (associating labellings to extensions) given in Definition 5.1. of [21].

An ADF interpretation, on the other hand, can be represented as an extension via the following mapping.

The two subsequent lemmas are adopted from [21].

Note that Lemma 13 does not mention admissible semantics, while Lemma 14 does. The reason is that for a given SETAF F the associated three-valued interpretations obtained via Ext2IntF usually do not cover all admissible interpretations of the ADF DF. This is illustrated next.

One can overcome this problem by mapping each admissible set e of a SETAF F=(A,R) to several interpretations in a way that Ext2IntF(e)(a) yields either u or f in case there exists (B,a)∈R such that B⊆e, and for all (B′,c) with a∈B′ and c∈e there exists (b≠a)∈B′ such that Ext2IntF(e)(b)=f. That is, Ext2IntF(e)(a) can be either f or u, if a is attacked by some arguments of e but the truth value of a does not play any role for the truth value of elements of e. However, since the forthcoming results do not involve admissible semantics, we leave a more formal investigation on this issue as topic for future work.

The next lemma rephrases Lemma 7 in terms of SETAFs.

The following corollary is a direct result of Lemma 15.

We are now in position to derive that symmetric SETAFs are neither coherent nor relatively grounded from our proof of Theorem 8.

3.4.The role of odd-length cycles

In [15] it is proven that if an AF is not coherent then it contains a cycle of odd length. This means, on the other hand, that if an AF does not contain any odd-length cycle it is coherent. It is easy to show that this property does not generalise to ADFs because of the possibility of support links. Indeed, consider the ADF D=({a,b,c,d},{φa=d,φb=a,φc=b,φd=c}). The interpretation v={a↦t,b↦t,c↦t,d↦t} is a two-valued (and, hence, preferred) model of D, however it is not a stable model. That is, D is not weakly coherent and, therefore, also not coherent.

In this section we study whether the property of having only odd-length-cycles implying coherence carries over to any subclasses of ADFs we introduced in our work so far. In Section 3.2 we had shown that ASSADFs are weakly coherent but not semi-coherent. We here show that also ASSADFs not containing any odd-length-cycle are not semi-coherent and, thus, that such ASSADFs are not coherent (Theorem 18). On the other hand, we are able to show that SFSADFs not containing any odd-length-cycle are coherent (Theorem 19). In fact we prove a more general result: bipolar ADFs without supporting links, which we dub SFADFs (Definition 20; note the difference with SFSADFs which have an “S” after the first “F”), that also do not have any odd-length-cycle are coherent (Corollary 20). Moreover, given that SETAFs correspond to a special class of SFSADFs (see Section 3.3), the result also applies to SETAFs.

Contrarily, we show next that the subclass of SFSADFs in which each ADF does not contain any odd cycle is coherent.

As it turns out, the proof of Theorem 19 is independent form the notion of symmetry. Hence, we obtain as a final observation (Corollary 20) in this section that the general class of support-free ADFs which we define next is coherent.