You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.

# Investigating subclasses of abstract dialectical frameworks

#### Abstract

Abstract dialectical frameworks (ADFs) are generalizations of Dung argumentation frameworks where arbitrary relationships among arguments can be formalized. This additional expressibility comes with the price of higher computational complexity, thus an understanding of potentially easier subclasses is essential. Compared to Dung argumentation frameworks, where several subclasses such as acyclic and symmetric frameworks are well understood, there has been no in-depth analysis for ADFs in such direction yet (with the notable exception of bipolar ADFs). In this work, we introduce certain subclasses of ADFs and investigate their properties. In particular, we show that for acyclic ADFs, the different semantics coincide. On the other hand, we show that the concept of symmetry is less powerful for ADFs and further restrictions are required to achieve results that are similar to the known ones for Dung’s frameworks. A particular such subclass (support-free symmetric ADFs) turns out to be closely related to argumentation frameworks with collective attacks (SETAFs); we investigate this relation in detail and obtain as a by-product that even for SETAFs symmetry is less powerful than for AFs. We also discuss the role of odd-length cycles in the subclasses we have introduced. Finally, we analyse the expressiveness of the ADF subclasses we introduce in terms of signatures.

## 1.Introduction

Since the landmark paper by Dung [13] has been published in 1995, abstract argumentation frameworks (AFs) have gained more and more significance in the AI domain. First of all, AFs have proven useful to capture the essence of different nonmonotonic formalisms. Moreover, AFs are nowadays an integral concept in several advanced argumentation-based formalisms in the sense that their semantics are defined based on a translation (typically called an instantiation) to Dung AFs. Finally, the relevance of AFs is witnessed by the International Competition on Computational Models of Argumentation (ICCMA), where systems for solving different problems on AFs compete on different tracks.1

The fundamental of Dung is to abstract away from the content of particular arguments and to focus only on conflicts among arguments, where each argument is viewed as an atomic item. Therefore, the only information AFs take into account is whether an argument attacks another one or not. Semantics single out coherent subsets of arguments which “fit” together, according to specific criteria [2]. More formally, an AF semantics takes an argumentation framework as input and produces as output a collection of sets of arguments, called extensions. Complexity of the reasoning problems that can be defined for the several semantics for AFs is well understood [17] and ranges from tractability up to the second level of the polynomial hierarchy. To this end, the analysis of restricted classes of AFs is of importance. In his paper, Dung already showed that the class of acyclic (also known as well-founded) AFs leads to a collapse of the different semantics. Further studies include symmetric AFs [10] and AFs under other graph-driven restrictions [14]. Symmetric AFs have been proven to satisfy the property of coherence (preferred and stable semantics coincide) and relatively-groundedness (the grounded extension is given by the intersection of the preferred extensions). Moreover, these restrictions make decision problems often easier from a complexity perspective. A fact that is particularly useful in connection with backdoor approaches [20] that utilize the distance to an easier fragment. This approach has, for instance, been realised in practice with the cegartix system [19].

Abstract dialectical frameworks (ADFs) are generalizations of Dung argumentation frameworks where arbitrary relationships among arguments can be formalized via propositional formulas which are attached to the arguments [5,8]. This allows to express notions of support, collective attacks, and even more complicated relations. Due to their flexibility in formalizing relations between arguments, ADFs have recently been used in several applications [1,9,26,30]. However, this additional expressibility comes with the price of higher computational complexity [35]. Specifically, reasoning in ADFs spans the first three (rather than the first two, as for AFs) levels of the polynomial hierarchy.

It is thus natural to investigate subclasses of ADFs. Compared to Dung argumentation frameworks, where subclasses like acyclic and symmetric AFs have been thoroughly studied, there has not been a systematic investigation of subclasses of ADFs yet. An exception is the class of bipolar ADFs [8] where the links between arguments are restricted to have either supporting or attacking nature. However, results about structural restrictions on ADFs where different semantics coincide are still lacking.

Our results lead to the following implications. Firstly, studying subclasses of ADFs provides us with a better understanding of which structures are required to reveal particular behaviors of the different semantics. We thus further advance the theory of ADFs. Secondly, since other generalizations of Dung AFs can be seen as special case of ADFs, results on ADFs carry over to these special cases. We exemplify this aspect in the paper, by deriving new results for argumentation frameworks with collective attacks (SETAFs) [27] which have received increasing interest recently [18,21]. To the best of our knowledge concepts like symmetric SETAFs have not been investigated yet, and we provide first results in this direction.

The paper is structured as follows: In Section 2, we first recall the relevant background of AFs, SETAFs, and ADFs. Then in Section 3 we introduce subclasses of ADFs and we investigate whether these subclasses fulfill the same properties of the similar subclasses in AFs. We discuss how our results can be related to SETAFs and investigate some properties for symmetric SETAFs. Also the role of odd-length cycles is addressed. In Section 4, expressiveness of the subclasses of ADFs introduced in the current work is studied. In particular, we show that the expressiveness of SFSADFs, ASSADFs and bipolar ADFs is equal for some of the semantics, but different for admissibility-based semantics.

A preliminary version of this article appeared in [11]. This extended version contains new technical results including investigations concerning coherence and relatively-groundedness for SFSADFs and symmetric SETAFs (Theorems 8 and 17); and results on the role of odd-cycles on coherence for subclasses of ADFs (Section 3.4). Also, the results on expressibility for SETAFs and SFSADFs (as well as for a further superclass of SFSADFs we introduce, that of SFADFs) in Section 4 are new.

## 2.Preliminaries

Let us start by recalling basic notions of Dung’s argumentation frameworks (AFs) and their extension for modelling collective attacks (SETAFs). We then introduce the formalism that is the focus of this work, abstract dialectical frameworks (ADFs), and point out a few elemental relations between ADFs, SETAFs, and AFs.

### 2.1.Abstract argumentation frameworks

#### Definition 1([13]).

An abstract argumentation framework (AF) is a pair (A,R) in which A is a set of arguments and RA×A is a binary relation representing attacks among arguments.

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,bA, 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 bA is attacked by a set SA if there is a aS that attacks b. An argument aA is, on the other hand, defended by a set SA of arguments (alternatively, the argument is acceptable with respect to S) (in F) if for each argument cA, it holds that if (c,a)R then there is a sS 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,bS 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)={aA|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:

##### Definition 2.

Let F=(A,R) be an AF. A set S which is conflict-free in F is:

• admissible in F iff SΓF(S);

• complete in F iff S=ΓF(S);

• grounded in F iff S is the ⊆-least fixed-point of ΓF;

• preferred in F iff S is ⊆-maximal admissible (resp. complete) in F;

• a stable model of F iff for all aAS, S attacks a.

In order to denote the collection of all conflict-free sets, (admissible sets, complete sets, grounded sets, preferred sets, stable models) of an AF F, we use the notation σ(F) where σ{cf,adm,com,grd,prf,stb}. Such sets are usually called extensions; we will also often refer to them as extension-sets or simply σ-sets (of arguments) where σ is a semantics.

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

##### Definition 3.

A set argumentation framework (SETAF) is an ordered pair F=(A,R), where A is a finite set of arguments and R(2A{})×A is the attack relation.

Given a SETAF (A,R), we write SRb if there is a set SS attacking b, i.e. (S,b)R. We say that in this case also S attacks b. Moreover, we write SRS if SRb for some bS. 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 SA is conflicting in F if SRS; SA 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 aA is defended (in F) by a set SA if for each BA, such that BRa, also SRB. A set T of arguments is hence defended (in F) by S if each aT 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)={aA|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):

##### Definition 4.

Let F=(A,R) be a SETAF. A set S which is conflict-free in F is

• admissible in F iff SΓF(S);

• complete in F iff S=ΓF(S);

• grounded in F iff S is the ⊆-least fixed-point of ΓF;

• preferred in F iff S is ⊆-maximal admissible (resp. complete) in F;

• a stable model of F iff for all aAS, S attacks a.

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:

#### Definition 5([8]).

An abstract dialectical framework (ADF) is a tuple D=(S,L,C) where;

• S is a finite set of nodes (arguments, statements, positions),

• LS×S is a set of links,

• C={φs}sS is a collection of propositional formulas (acceptance conditions).

The variables occurring in each acceptance condition φsC are taken from the parents of s, par(s)={aS(a,s)L}. Thus the arguments of an ADF act at the same time as nodes of the ADF and variables in the acceptance conditions. An argument sS is called initial if par(s)=.

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 sS. 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 ab.

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, V2V, 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 uit and uif. An interpretation v is at least as informative as another interpretation w, denoted by wiv, if w(s)iv(s) for each sS. As usual w<iv whenever wiv but it is not the case that viw. The meet operator i on truth values is defined as tit=t, fif=f and returns u otherwise. The meet i of two interpretations v and w is then defined as (viw)(s)=v(s)iw(s) for each sS. 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

ΓD(v)=vsuch that v(s)=tif φsv is irrefutable (i.e., a tautology),fif φsv is unsatisfiable,uotherwise,
where the partial valuation of φs by v, is given by φsv=v(φs)=φs[p/:v(p)=t][p/:v(p)=f]. Here ppar(s). We will also sometimes write that sS is acceptable w.r.t. v (in D) if φsv is irrefutable. On the other hand sS is deniable w.r.t. v (in D) if φsv is unsatisfiable. Importantly, the characteristic operator for ADFs is monotonic: if wiv for a given ADF D, then also ΓD(w)iΓD(v).

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

##### Definition 6.

Given an ADF D=(S,L,C), an interpretation v is

• conflict-free in D iff v(s)=t implies φsv is satisfiable and v(s)=f implies φsv is unsatisfiable;

• admissible in D iff viΓD(v);

• complete in D iff v=ΓD(v);

• grounded in D iff v is the least fixed-point of ΓD;

• preferred in D iff v is i-maximal admissible (resp. complete) in D;

• a (two-valued) model of D iff v is two-valued and for all sS, it holds that v(s)=v(φs);

• a stable model of D if v is a model of D and vt=wt, where w is the grounded interpretation of the stb-reduct Dv=(Sv,Lv,Cv), where Sv=vt, Lv=L(Sv×Sv), and φs[p/:v(p)=f] for each sSv.

As for AFs and SETAFs, the set of all σ interpretations for D is denoted by σ(D), where σ{cf,adm,com,grd,prf,mod,stb} abbreviates the different semantics in the obvious manner.

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.

##### Definition 7.

• supporting (in D) if for every two-valued interpretation v, v(φa)=t implies v|tb(φa)=t;

• attacking (in D) if for every two-valued interpretation v, v(φa)=f implies v|tb(φa)=f;

• redundant (in D) if it is both attacking and supporting;

• dependent (in D) if it is neither attacking nor supporting.

##### 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:ab¬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.

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={au,bu,ct} is conflict-free. However, v is not an admissible interpretation, because ΓD(v)={au,bu,cu}, that is, v≰iΓD(v). The interpretation v1={af,bu,cu} on the other hand is an admissible interpretation and, in fact, also the unique grounded interpretation of D. Further, prf(D)=mod(D)={{af,bf,ct},{af,bt,ct}}, but only the first interpretation in this set is a stable model. This is because for v={af,bf,ct} the unique grounded interpretation w of Dv is {ct} and vt=wt. The interpretation v={af,bt,ct} is not a stable model, since the unique grounded interpretation w of Dv is {bu,ct} and vtwt. 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 sS is of the form φs=apar(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.

##### Definition 8.

Let F=(A,R) be an AF. The associated ADF of F is DF=(S,L,C) in which S=A, L=R, and the acceptance condition of each sS in C is given as φs=a:(a,s)R¬a.

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

##### Definition 9.

Let F=(A,R) be a SETAF. The ADF associated to F is a tuple DF=(S,L,C) in which, S=A, L=R and C={φa}aS is the collection of acceptance conditions defined, for each aS, as

φa=(B,a)RaB¬a.

We start our investigation of ADF subclasses in terms of their semantics by first introducing the class of acyclic ADFs and showing that, just as is the case for acyclic AFs [13], the different semantics coincide on such ADFs. Then, we consider symmetric ADFs, where we will explore further restrictions that are needed in order to obtain results similar to the ones known for symmetric AFs. In Section 3.3 we discuss implications of our results for SETAFs. We conclude this section with a brief overview on semantic properties of odd-cycle free subclasses of 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.

##### Definition 10.

An ADF D=(S,L,C) is acyclic if its corresponding directed graph (S,L) is acyclic.

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.

##### Proposition 1.

In every acyclic ADF D the i-least fixed point of ΓD is a model of D.

##### Proof.

Let D=(S,L,C) be an acyclic ADF and let m be its maximum level. Moreover, let v0:=vu and vi:=ΓD(vi1) for 1im. We claim that for all i with 1im, and every argument sj with level ji it holds that either vi(sj)=t or vi(sj)=f. We show this claim by induction on i:

• Base case: Suppose s1 is an arbitrary argument of level one (an acyclic ADF always includes an initial argument). Since s1 is an initial argument, either φs1= or φs1=. Hence v1(s1)=ΓD(v0)(s1) is either true or false.

• Inductive step: Assuming this property holds for all k with 1ki<m, we show it holds for i+1. We know that φsjvi=φsj[sk/:vi(sk)=t][sk/:vi(sk)=f]. For all sk that occur in φsj it holds that k<ji+1, with k being the level of sk. Therefore, by the inductive hypothesis, for each sk, either vi(sk)=t or vi(sk)=f. Hence either φsjvi or φsjvi and, consequently, either vi+1(sj)=t or vi+1(sj)=f.

Since m is the maximum level of any argument in D, we now get that vm(s) is either true or false for all sS, i.e. it is a two-valued interpretation. Moreover, it holds that vm=ΓD(vm), i.e. vm is a fixed point.

To show that vm is the least fixed point of ΓD, assume, towards a contradiction, that there exists an interpretation v<ivm such that v=ΓD(v). Then there exists an argument s such that either vm(s)=t or vm(s)=f, but v(s)=u. Assume s has level i. Since D is an acyclic ADF all arguments sk that occur in φs have a level less than i. Therefore, there exists at least an argument sj of level j<i in φs such that v(sj)=u. By iterating this method after at most i1 times we reach an argument s1 of level 1 for which v(s1)=u. This is a contradiction, since at level 1 all arguments are initial, it must be the case that either φs1= or φs1=, and therefore ΓD(v)(s1)u. Thus, interpretation vm is the least fixed point of ΓD. □

##### Theorem 2.

In every acyclic ADF D the sets of grounded interpretations, complete interpretations, preferred interpretations, two-valued models, and stable models coincide.

##### Proof.

First, the grounded interpretation v of D is also complete in D. Moreover, Proposition 1 implies that v is a two-valued model of D. Since w=wt=vt in which w=grd(Dv), v is a stable model. It remains to show that there is no further complete interpretation v of D. Since v is two-valued it must hold that viv. However, since v is grounded and therefore the least complete interpretation, such a v cannot exist. Therefore, v is the unique complete interpretation of D which is grounded, stable, two-valued, and preferred. □

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.

##### Example 3.

Consider the ADF D=({a,b,c},{φa=,φb=¬a¬c,φc=¬b}). This ADF possesses the unique complete interpretation v={at,bf,ct}, which is also preferred, stable, grounded, as well as a model of D. That is, all semantics of D coincide; however, D is not acyclic.

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.

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.

##### Definition 11.

An ADF D=(S,L,C) is symmetric if L is irreflexive and symmetric and L does not contain any redundant links.

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(¬bb). 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.

##### Definition 12.

• coherent if each preferred interpretation of D is a stable model of D;

• weakly coherent if each two-valued model of D is a stable model of D;

• semi-coherent if each preferred interpretation of D is a two-valued model of D.

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

##### Definition 13.

An ADF D is called relatively grounded if grd(D)=iprf(D).

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.

##### Theorem 3.

The class of symmetric ADFs is neither semi-coherent, nor weakly coherent, nor relatively grounded.

##### Proof.

Let D be the symmetric ADF depicted in Fig. 3. It holds that prf(D)={v1,v2} with v1={at,bt,ct,dt,ef} and v2={at,bf,cf,du,eu}. Since v1 is a two-valued model of D which is not stable (since Dv=D and grd(D)={vu}), D is not weakly coherent. Also, D is not semi-coherent since v2 is not two-valued. In addition, iprf(D)=v2={at,bu,cu,du,eu}, but grd(D)={vu}. Therefore, D is not relatively grounded. □

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

##### Definition 14.

Given an ADF D=(S,L,C), let L+ be the set of all supporting links in D. An ADF D is an acyclic support symmetric ADF (ASSADF for short) if it is symmetric, bipolar and (S,L+) is acyclic.

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.

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

##### Lemma 4.

Let D be an ADF, v a two-valued model of D, and sS an argument such that all parents of s are attackers. If φsv is irrefutable then φs[si/:v(si)=f] is irrefutable.

##### Proof.

Let D=(S,L,C) be an acyclic support symmetric ADF. We have to show that each two-valued model of D is also a stable model of D. Let hence v be a two-valued model of D, Dv=(Sv,Lv,Cv) be the stb-reduct of D, w be the unique grounded interpretation of Dv, and φs the acceptance condition of s in Dv, i.e. φs=φs[si/:v(si)=f]. We show that vt=wt. Suppose to the contrary that there exists an argument s, such that v(s)=t and w(s)t. That is, φs is not irrefutable. This means, by Lemma 4, that φs contains an argument s1 supporting s such that v(s1)=t, otherwise φs cannot be irrefutable. Thus, φs also contains s1. Since supports are acyclic in ASSADFs, for the same reasons φs1=φs1[si/:v(si)=f] contains an argument s2 which is different from s and s1 and which supports s1. Thus there exists an infinite sequence of arguments s1,s2, such that si+1 supports si. This is a contradiction to D being an ASSADF. □

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

##### Theorem 6.

The class of ASSADFs is neither semi-coherent nor relatively grounded.

##### Proof.

Consider the ASSADF D depicted in Fig. 5. D has 4 preferred interpretations, namely v1={af,bf,ct,dt,ef}, v2={af,bt,cf,dt,ef}, v3={at,bf,cf,dt,ef}, and v4={au,bu,cu,df,et}. 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.

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={af,bf,ct} and v2={af,bt,cf}. We obtain v1iv2={af,bu,cu}. However, the grounded interpretation of D is the trivial interpretation vu. That is, D is not relatively grounded. □

### 3.3.Implications for SETAFs

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

##### Definition 15.

Given an ADF D=(S,L,C), let L be the set of all attacking links in D. A bipolar ADF D=(S,L,C) is a support free symmetric ADF (SFSADF for short) if it is symmetric and does not have any supporting links, that is, L=L.

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.

##### Lemma 7.

Let D be an SFSADF with no isolated argument. The unique grounded interpretation of D is the trivial interpretation, vu.

##### Proof.

We show that for any SFSADF D=(S,L,C) with no isolated argument, ΓD(vu)=vu. Let s be an argument. Let v1 be an interpretation in which all parents of s are assigned to t and let v2 be an interpretation in which all par(s) are assigned to f. Since D is an SFSADF, the former interpretation shows that φsvu is not irrefutable and the latter interpretation says that φsvu is not unsatisfiable. Therefore, for each argument s, ΓD(vu)(s)=u. □

##### Theorem 8.

The following are the case for SFSADFs:

• every SFSADF is weakly coherent,

• the class of SFSADFs is not semi-coherent,

• the class of SFSADFs is not relatively grounded.

##### Proof.

The ASSADF D, depicted in Fig. 5 to show that the class of ASSADFs is not semi-coherent, does not have any supporting links. That is, D is a SFSADF. Thus, the class of SFSADFs is not semi-coherent either.

It remains to show that the class of SFSADFs is not relatively grounded. Let D be the ADF depicted in Fig. 7. The unique preferred interpretation of D is v={at,bf,cf,dt}. However, since D does not possess an isolated argument, Lemma 7 shows that the grounded interpretation of D is the trivial interpretation. That is, the meet of the preferred interpretations of D is not equal to the grounded interpretation of D. Hence, D is not relatively grounded. □

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

##### Definition 16.

A SETAF F=(A,R), in which R(2{}×A), is a symmetric SETAF if the following properties hold:

• for all (S,t)R and for all sS, there exists (T,s)R such that tT,

• for each argument s and for each (S,s)R, the set S does not include s,

• for each (S,s)R there is no (S,s)R with SS.

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.

##### Proof.

Let F=(A,R) be a symmetric SETAF. We show that the ADF DF=(S,L,C) associated to F is a SFSADF. By Definition 9, DF does not contain any supporting link. It remains to show that DF is a symmetric ADF. By Definition 16, it is clear that L does not have any redundant links. We hence show that L is symmetric and irreflexive. Towards a contradiction, thus assume that either L is not symmetric or not irreflexive.

• Assume that L is not symmetric. This means that there is an argument s which is a parent of t but not visa versa. That is, s appears in the acceptance condition of t but t does not appear in the acceptance condition of s. Since s is a parent of t, by Definition 9 there is (S,t)R such that sS. Since F is a symmetric SETAF, there is a (T,s)R such that tT. Then, again via Definition 9, the argument t appears in the acceptance condition of s. Thus, t is a parent of s. This shows that the assumption that L is not symmetric is false.

• Assume now that L is not irreflexive. Therefore, there is an argument s which is contained in par(s). By Definition 9 there is (S,s)R such that sS which is in contradiction to F being symmetric, cf. Definition 16.

Thus, if F is a symmetric SETAF, then the associated ADF DF is a SFSADF. □

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)RaB¬a. On the other hand, if there exists (B,a)R, it holds that φa=(B,a)RaB¬a. These facts together with Theorem 9 lead to the following corollary.

##### Corollary 10.

The SFSADF associated to a given symmetric SETAF does not contain any argument with an unsatisfiable acceptance condition.

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.

##### Lemma 11.

Let D=(S,L,C) be a SFSADF and let sS be an argument that is not isolated. Then the acceptance condition of the argument s can be written in conjunctive normal form and having only negative literals.

##### Proof.

Since the acceptance condition of each argument in an ADF is indicated by a propositional formula, it can be transformed to CNF. It remains to show that each of the resulting formulas in CNF consists of only negative literals. Toward a contradiction assume that φs is the acceptance condition of an argument s, that is not isolated, in conjunctive normal form that contains positive literals. Without loss of generality assume that t is the only argument that appears in φs as a positive literal. Let {cti}1in be the set of all clauses cti in which t occurs (n1). Also, let v be a two-valued interpretation which assigns the truth value f to t; all other arguments in each cti is assigned to t. Also v assigns f to all other arguments of par(s), which means that v(φs)=f. However, v|tt(φs)=t. Thus, by the definition of attacking links, (t,s) is not an attacking link in D. This is a contradiction with D being a SFSADF. □

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

##### Definition 17.

Let D=(S,L,C) be a SFSADF in which there is no argument having an unsatisfiable acceptance condition. D can be written as a SETAF FD=(A,R) such that A=S and R is as follows. Let φa be in CNF having only negative literals, let c be a clause of φa and let Rc be the set of all arguments in the clause c. Then, (Rc,a) represents a joint attack to a. The set Ra={(Rc,a)|c is a clause in φa} is the set of all joint attacks to an argument a. Let R=aSRa, be the set of all joint attacks in FD. We call FD the SETAF associated to D.

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.

##### Theorem 12.

Let D=(S,L,C) be a SFSADF in which the acceptance condition of none of the arguments is unsatisfiable. The SETAF FD associated to D is a symmetric SETAF.

##### Proof.

Assume that D is a SFSADF in which there is no argument with an unsatisfiable acceptance condition. Thus, via Definition 17, D can be written as a SETAF FD=(A,R). It remains to show that FD is a symmetric SETAF. Towards a contradiction, assume that FD is not symmetric. Then, there are two possibilities to consider:

• There exists (S,t)R and there exists sS such that for all (T,s)R, T does not include t. Therefore, the acceptance condition of t in D includes s, however, the acceptance condition of s in D does not include t. That is, L in D is not symmetric.

• There exists (S,t)R such that tS. That is, t appears in the acceptance condition of t in D. That is, L in D contains a reflexive link.

Both possibilities are in contradiction with the assumption that D is a SFSADF. Therefore, the assumption that FD is not symmetric is not true. Then, the SETAF associated to a SFSADF is a symmetric SETAF. □

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

##### Definition 18.

Let F=(A,R) be a SETAF, and let e be an extension of F (eE). The truth value assigned to each argument aA by the three-valued interpretation ve associated to e is given by the function Ext2IntF:EV as follows.

Ext2IntF(e)(a)=tae,fB2A such that (B,a)R and bB,be,uotherwise.

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

##### Definition 19.

Let D=(S,L,C) be an ADF and v an interpretation of D, that is, vV. The associated extension ev of v is obtained via application of the function Int2ExtD:VE on v, as follows:

Int2ExtD(v)={sS|stv}

The two subsequent lemmas are adopted from [21].

##### Lemma 13.

Let F be a SETAF, and σ{prf,stb,mod,com,grd}. Moreover, let DF be the ADF associated to F. Then, σ(DF)={Ext2IntF(e)eσ(F)}.

##### Lemma 14.

Let D be a SFSADF in which the acceptance condition of none of the arguments is unsatisfiable, σ{adm,prf,stb,mod,com,grd} and FD the SETAF associated to D. Then, σ(FD)={Int2ExtD(v)vσ(D)}.

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.

##### Example 5.

Let F=({a,b,c},{{a,b},c}) be a SETAF. By Definition 9, the associated ADF to F is DF=({a,b,c},{φa=,φb=,φc=¬a¬b}). It is clear that e={a,b}adm(F). Applying Ext2IntF(e) of Definition 18 to e leads to the three-valued interpretation ve={at,bt,cf}. However, {at,bt,cu} is also an admissible interpretation of DF which is not obtained from any admissible extension e of F via Ext2IntF(e).

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 Be, and for all (B,c) with aB and ce there exists (ba)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.

##### Lemma 15.

Let F be a symmetric SETAF with no isolated argument. The unique grounded extension of F is the empty set.

##### Proof.

Let F=(A,R) be a symmetric SETAF with no isolated argument, and let DF=(S,L,C) be the associated ADF of F. Toward a contradiction assume that the unique grounded extension e (in F) is not the empty set, that is, there exists argument a such that ae. First, we show that DF does not contain any isolated argument. To this end, let b be an argument. Since F does not contain any isolated argument, there exists BA such that (B,b)R. The associated acceptance condition of b in DF, namely φb=(B,b)RbB¬b shows that par(b){} in DF. Thus, the associated DF does not contain any isolated argument, as well. By Lemma 13 and Definition 18, a is assigned to t in grd(DF). Further by Theorem 9, DF is an SFSADF. This is a contradiction by Lemma 7. Therefore, the unique grounded extension of F is the empty set. □

The following corollary is a direct result of Lemma 15.

##### Corollary 16.

A symmetric SETAF F with no isolated argument is relatively grounded if and only if the intersection of all preferred extensions of F is the empty set.

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

##### Theorem 17.

The class of symmetric SETAFs is neither coherent nor relatively grounded.

##### Proof.

The ADFs which are used in the proof of Theorem 8, to show that the class of SFSADFs is neither semi-coherent (and thus not coherent) nor relatively grounded, do not consist of any argument with an unsatisfiable acceptance condition. Then, by Theorem 12, the associated AFs to those SFSADFs are symmetric SETAFs.

Now, let D be such an SFSADF that does not satisfy coherence. We show that the SETAF FD associated to D cannot be coherent either. Let w be a preferred interpretation of D that is not a stable model of D. By Lemma 14, prf(FD)={Int2ExtD(v)vprf(D)} and stb(FD)={Int2ExtD(v)vstb(D)}. Towards a contradiction, suppose prf(FD)=stb(FD). It follows that there is an interpretation uprf(D) with ut=wt, such that ustb(D), and hence uw. Hence, either ufwf or wfuf. In the first case u<iw and hence u cannot be preferred; in the second case w<iu and hence w cannot be preferred. In both cases we have a contradiction.

For relatively groundedness, we already have provided a symmetric SETAF that violates this property in Fig. 8. For that SETAF it can be checked that its complete sets are and {a,d}. Corollary 16 immediately implies that this SETAF cannot be relatively grounded. □

### 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={at,bt,ct,dt} 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.

##### Theorem 18.

The subclass of ASSADFs not containing any odd-length cycle is not coherent.

##### Proof.

Consider the ADF D=({a,b},{φa=b,φb=¬a}). D is an ASSADF in which there is no odd cycle. The unique preferred interpretation of D is v={au,bu}, however, v is not a two-valued model. Then, D is not semi-coherent and D is not coherent either. □

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

##### Theorem 19.

The class of SFSADFs that do not contain any odd-length cycle is coherent.

##### Proof.

Let D=(S,L,C) be a SFSADF that does not contain any odd cycle. Since we showed in Theorem 8 that the class of SFSADFs is weakly coherent, D is weakly coherent, as well. To complete the proof of the theorem it is enough to show that D is semi-coherent, i.e. prf(D)=mod(D). Since each two-valued model is a preferred interpretation of ADFs, it is trivial that prf(D)mod(D). Thus, it is enough to show that prf(D)mod(D). Toward a contradiction, assume that there exist a preferred interpretation v of D that is not a two-valued model. That is, there must exist an argument a such that v(a)=u.

Let S be the set of all arguments which are assigned the truth value u by v. Since D is a SFSADF that does not contain any odd cycle, the arguments of S have to be in even cycles in the associated graph. Without loss of generality, assume that the associated graph of D contains only one such even cycle. Then one can construct a bipartite graph of nodes of this cycle with partitions S1 and S2. Assign all arguments in S1 to t, and all arguments of S2 to f. Construct the interpretation v as follows.

v(a)=v(a)if v(a)=t/f,tif aS1,fif bS2.

It is clear that viv. We now show that v is a two-valued model. First, there is no argument in v assigned to u. To show that v is a two-valued model it remains to show that ΓD(v)=v. Assume that a is assigned to t in v, we show that ΓD(v)(a)=t. (The method for proving the case that a is assigned to f is analogous.) If at in v either v(a)=t or aS1.

• If v(a)=t, since v is a preferred interpretation, ΓD(v)(a)=t. In addition, the characteristic operator is a monotonic operator, that is, ΓD(v)(a)=t.

• If aS1, then par(a){}. Let φa be in CNF, this is possible by Lemma 11.

• If ΓD(v)(a)=f, then there exists a clause c in φa all arguments of which are assigned to t in v. By the construction of S1, par(a)S1. Therefore, all arguments of c are assigned to t in v (note that all arguments in S2 are assigned to f by the definition of v). That is, ΓD(v)(a)=f, which is a contradiction with the assumption that v(a)=u. Thus, ΓD(v)(a)f.

• If ΓD(v)(a)=u, then there exists a parent of a the truth value of which is not indicated in v. This is also a contradiction, since all parents of a are either in S2 that are assigned to f in v or assigned to t/f by v. Therefore, ΓD(v)(a)u.

Thus, if aS1, then ΓD(v)(a)=t.

Therefore, v is a two-valued model of D and hence a preferred interpretation of D. Moreover viv, which is a contradiction to the assumption that v is a preferred interpretation. Therefore, each preferred interpretation of a SFSADF that does not contain any odd cycle is a two-valued model. Thus, if a SFSADF does not contain any odd cycle, then it 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.

##### Definition 20.

Given an ADF D=(S,L,C), let L be the set of all attacking links in D. A bipolar ADF D=(S,L,C) is called a support-free ADF (SFADF) if it does not have any supporting links, that is, L=L.

##### Corollary 20.

SFADFs and SETAFs without odd-length cycles are coherent.

Following the work of [16] in this section we consider the expressiveness, i.e. the set of possible outcomes which can be achieved under the different semantics, of ASSADFs and SFSADFs. We thus complement here results that have been obtained for general [29,33] and bipolar ADFs [25] and also compare the ADF subclasses we introduced in this work to abstract argumentation frameworks in terms of their expressivity.

Formally, the study of expressivity of a formalism w.r.t. a semantics can be done by considering the outcomes that can be realised by the formalism under the semantics of interest.

##### Definition 21.

Let F be a formalism (e.g. AFs or (subclasses of) ADFs), i.e. the set of structures available in F (e.g. all possible AFs and ADFs) and σ a semantics for F. Moreover, let V be an interpretation-set or extension-set. V is said to be σ-realizable in F, if there exists an element kb (“knowledge base”) of F such that σ(kb)=V.

The signature of a formalism w.r.t. a semantics is then the set of possible outcomes that can be realised by the formalism under the semantics, this is encoded in Definition 22.

##### Definition 22.

The signature ΣFσ of a formalism F w.r.t. a semantics σ is defined as:

ΣFσ={σ(kb)| kbF}.
Formalisms can now be compared for expressivity by considering their signatures. Specifically, given two formalisms F1, F2 as well as a semantics σ, we say that F1 is strictly more expressive than F2 for σ, whenever ΣF2σΣF1σ. F1 and F2 are, on the other hand, incomparable under a semantics σ if neither ΣF1σΣF2σ nor ΣF2σΣF1σ. This is denoted as ΣF1σΣF2σ.

In what follows we concentrate on studying ASSADFs and SFSADFs from the perspective of realisability. We compare these novel subclasses of ADFs to that of AFs, BADFs, and general ADFs. We build on studies comparing the expressivity of AFs, BADFs and (general) ADFs reported on in [25,32].

We begin by showing that BADFs are strictly more expressive than ASSADFs for the admissible, preferred, complete, and model semantics.

##### Proof.

For σ{prf,mod}, let V={{at},{af}}, and for σ{com,adm}, let V={{au},{at},{af}}. The BADF D=(S,L,C) with S={a} and φa=a realizes V under σ and V under σ. On the other hand, it is easy to check that there is no ASSADF with one argument which realizes V under σ, and respectively, V under σ. To complete the proof toward a contradiction assume that there exists an ASSADF D=(S,L,C) such that σ(D)=V and σ(D)=V. Since V contains an assignment to only one argument, D has to have just one argument. Since D is an ASSADF, the argument a is an isolated argument in D. That is, either φa= or φa=. Thus, it can realize neither V under σ nor V under σ. □

Next, we show that ASSADFs are strictly more expressive than SFSADFs for the admissible, preferred, and complete semantics. In a certain sense, this complements our observation in Section 3.4 that ASSADFs and SFSADFs differ in terms of coherence on odd-cycle free frameworks.

##### Proof.

Let V={{au,bu}}. The ASSADF D=(S,L,C) with S={a,b}, φa=b, and φb=¬a realizes V under σ{adm,prf,com}. However, it is easy to check that there is no SFSADF that can realize V. Assume to the contrary that there exists a SFSADF D=(S,L,C) that can realize V under σ, for σ{adm,prf,com}. The set of arguments of D is {a,b} as these are the only ones appearing in the σ interpretations of D.

• If any of the arguments of S is an isolated argument, then its acceptance condition is either equivalent to ⊤ or ⊥. That is, σ(D)V. Thus, none of the arguments could be an isolated argument in D.

• If there is a symmetric attack relation between a and b, then the interpretation {at,bf} is a preferred interpretation of D and therefore it is a complete and admissible interpretation of D. Therefore, σ(D)V, for σ{adm,prf,com}.

The forthcoming result shows why, on the other hand, AFs and SFSADFs are incomparable, and also AFs and ASSADFs are incomparable, in terms of their expressivity for the admissible, preferred, and complete semantics.

##### Proof.

∙ To show ΣAFσΣASSADFσ consider V={{au}}. A witness of σ-realizability in AFs is F=({a},{(a,a)}). However, there is no ASSADF to realize V under σ.

Our final result on the admissibility-based semantics concerns the class of support-free ADFs (SFADFs). Recall that support-free symmetric ADFs (SFSADFs) have been defined in Section 3.3 in order to investigate subclasses of symmetric ADFs that satisfy certain properties.

##### Proof.

We separately prove the four relations provided in the theorem.

• ΣAFσΣSFADFσ is clear. To show that ΣSETAFσΣAFσ, let V={{af}} for σ{prf,com}, and respectively let V={{au},{af}} for σ=adm. Both interpretation-sets are realizable by D=({a},{φa=}) in SFADF under σ. In contrast VΣAFσ.

• Each SFADF does not contain any dependent link; hence it is a BADF. The interpretations that are given in the proof of Theorem 21 work here to show that ΣBADFσΣSFADFσ. □

The general picture for the stable semantics, which we proceed to investigate now, deviates somewhat from that of the admissibility based semantics. To start we remind the reader that stable models v, w of any ADF are always incomparable, i.e. wtvt implies wt=vt, see [31]. Now, in order to complete previous results from [32] comparing AFs, BADFs and general ADFs in terms of their expressivity w.r.t. the stable semantics, we make use of this fact and the forthcoming lemma, in order to prove that ΣBADFstbΣSFSADFstb.

##### Lemma 25.

Any incomparable set of two-valued interpretations V is stb-realizable in SFSADFs.

##### Proof.

(sketch) To show that any incomparable set of two-valued interpretations is stb-realizable by some SFSADF, let V be an incomparable set over arguments S (that is, each vV assigns t or f to every sS) and consider a SFSADF D=(S,L,C) with the following acceptance conditions for sS:2

• If v(s)=t for every vV then φs.

• If v(s)=f for every vV then φs.

• Otherwise, φs=vV,v(s)=tv(t)=fwV:(w(s)=fw(t)=t)¬t.

We show that D is a SFSADF and stb(D)=V.
• By the definition of the acceptance condition of argument s in D, spar(s). Therefore, L is irreflexive. Further, tpar(s) iff spar(t), that is, L is symmetric. In addition, all links in D are attacking. Thus, D is a SFSADF.

• To prove that stb(D)=V, we show that stb(D)V and also Vstb(D).

• To show Vstb(D), let vV. We show that vmod(D) and since SFSADFs are weakly coherent by Theorem 8, vstb(D). Let v(s)=t, we show that s is acceptable in v. (The proof for the case that v(s)=f is analogous). If s is assigned t by each element of V there is nothing to prove. Otherwise, there exists a wV s.t. w(s)=f. Since V is incomparable, there exists t such that v(t)=f and w(t)=t. Therefore, tpar(s). The set of all arguments like t make a conjunctive clause of φs which guarantees that s is accepted in v.

• To show that stb(D)V, toward a contradiction, assume that there exists vstb(D) such that vV. Since stb(D) is incomparable, there exists sS such that v(s)=t and φs. Further, the acceptance condition of s is not unsatisfiable, otherwise s has to be assigned to f in v. Thus, there exists vV in which s is assigned to t. Let K be the set of all v in which s is assigned to t. Since vV and stb(D) is incomparable, in each vK there exists t such that v(t)=t and v(t)=f. Let T be a set of all arguments like t. It can be shown that either each conjunctive clause of φs contains a tT, or there exists a tT such that each conjunctive clause of φt consists of an argument of T. The former means that s is deniable with respect to v, and the latter means that t is deniable in v. That is, v is not a two-valued model of D and since SFSADFs are weakly coherent, v is not a stable model of D. This is in contradiction with our assumption that there exists vstb(D) such that vV. Therefore, stb(D)V. □

Note that the incomparability condition for the set of two valued interpretations V in the statement of Lemma 25 is necessary. For instance, V={{at},{af}} is a set of two-valued interpretations, which are not incomparable, that is not stb-realizable in SFSADFs.

##### Proof.

In Example 6 we give an example of an interpretation-set that is stb-realizable in SFSADFs but not stb-realizable in AFs.

##### Example 6.

Let V={{at,bt,cf},{af,bt,ct},{at,bf,ct}} be an interpretation-set. A witness of stb-realizability of V in SFSADFs is D=(S,L,C) for which S={a,b,c} and the acceptance conditions are φa=¬b¬c, φb=¬a¬c and φc=¬a¬b. We show that V is not stb-realizable in AFs. Towards a contradiction assume that there exists an AF F=(A,R) such that stb(F)=V. The set of arguments of F is S as these are the arguments occurring in stb(F). The interpretations in V imply that there is no link between a, b and c in F. Then, by the definition of the stable semantics for AFs, the interpretation {at,bt,ct} is also a stable interpretation of F. Therefore, stb(F)V. Thus, the interpretation-set V is not stb-realizable in AFs and ΣSFSADFstbΣAFstb

The final semantics to investigate is the model-semantics. We only need one technical lemma.

##### Lemma 27.

For any SFADF D=(S,L,C), mod(D) is incomparable.

##### Proof.

Toward a contradiction assume that there are v,wmod(D) such that vtwt. Let BS be the set of argument which are assigned to t in w, but are assigned to f by v. Moreover, let a be an argument which is denied in v and accepted in w. At least a parent of a has to be in B, otherwise, φav=φaw. Assume par(a)B={b1,,bn}. Since D is a SFADF, all links are attacking. Then, by the definition of attacking links v|tb1(φa)=f. That is, a is denied with respect to v1=v|tb1. Following the same method construct vi=v|tbi, for 1in. It is obvious that a is denied in each vi, in particular, a is denied in vn, which is equal to w. This is a contradiction to the assumption that a is accepted in w. Therefore, mod(D) is a set of incomparable interpretations. □

##### Proof.

Using these relations and observing that stb and mod are equivalent for AFs, it follows from Theorem 26 that ΣAFmodΣSFSADFmodΣSFADFmodΣASSADFmod holds. Finally, ΣASSADFmodΣBADFmod is by Theorem 21. □

Figure 10 summarises the results regarding expressivity w.r.t. the model and stable semantics expressed in Theorem 26 and Theorem 28. Again, to complete the picture we make use of results from [32] (ΣBADFstbΣADFstb and ΣBADFmodΣADFmod).

##### Fig. 10.

We conclude this section by pointing out that the realisability relationships depicted in Fig. 10 change when we restrict the cardinality of the interpretation sets. As it turns out, any set of interpretations of size 2 obtained from an ADF when evaluated using the stable semantics is also realizable in AFs.

##### Proposition 29.

Suppose that |V|=2 and V is stb-realizable in ADFs. Then V is stb-realizable in AFs.

##### Proof.

Let V={v1,v2} be a set of interpretations that is stb-realizable in ADFs, i.e. there exists an ADF D=(S,L,C) such that stb(D)=V. Construct an AF F=(A,R) by setting A=S and R={(a,b)vi(a)=t,vi(b)=f,vj(a)=f,1ij2}. To prove that stb(F)=V, take viV. First, there is no attack between arguments with vi(a)=t. Moreover, if vi(b)=f then, since neither v1iv2 nor v2iv1, there must be some aA with vi(a)=t and vj(a)=f, hence (a,b)R. Therefore vi is a stable interpretation of F. That is, V is stb-realizable in AFs. □

## 5.Discussion

Motivated by crucial results on the semantic properties of acyclic (or well founded) [13], symmetric [10], and odd-length-cycle-free [15] AFs, in this work we investigated analogous classes for ADFs and their properties. We showed that for acyclic ADFs, just as is the case for acyclic AFs, the different semantics coincide. On the other hand, we demonstrated that the properties of coherence and relatively-groundedness that hold for symmetric AFs do not carry over to symmetric ADFs. The latter impelled us to go on a quest for an appropriate subclass of symmetric ADFs for which some form of coherence holds. In the process we defined several subclasses, in particular acyclic support symmetric ADFs (ASSADFs) and support-free symmetric ADFs (SFSADFs) which we show satisfy a weaker form of coherence.

Also odd-length-cycle-free ADFs do not satisfy coherence (which is the case for AFs), but here we were able to show that this property does hold for SFSADFs. In fact this is the case for a superclass of SFSADFs (which also contains AFs with collective attacks), which we dubbed SFADFs. This property also allowed us to distinguish ASSADFs from SFSADFs in that odd-length-cycle-free ASSADFs are not coherent in general.

The motivation behind this line of investigation lies in the fact that different semantics show different complexities [35]. It is thus valuable to know under which circumstances higher complexities can be avoided. Acyclicity is a positive example since the coincidence with grounded semantics shows that, for instance, the more complex preferred semantics becomes easier for this class of frameworks. The practical implication is as follows: an ADF solver should check for acyclicity before computing preferred interpretations, since in case the ADF to be treated is acyclic, the easier procedure for grounded semantics suffices to do the job. As we have shown, such a strategy does not carry over to symmetric ADFs. This is in contrast to symmetric AFs where coherence holds, i.e. the (more complex) preferred semantics coincides with the (easier) stable semantics. Nonetheless, there is still a chance that symmetric ADFs are of practical help. In contrast to acyclic ADFs where the complexity drop is immediate, our results underline that dedicated complexity analyses for symmetric ADFs should be considered as future work.

This work is an elaboration on the more theoretical aspects of our work presented in [11]. There we had also included results on an empirical evaluation of some of the main systems for ADFs (QADF [12], YADF [3], and goDIAMOND [34]) on acyclic vs. non-acyclic ADFs. These show usually only a slight improvement of these systems (which do not detect subclasses of ADFs) on the acyclic instances despite the fact that the results we present in this work indicate that even the most difficult of reasoning problems become tractable for acyclic ADFs. Thus, our work offers further guidelines for designing more efficient systems for ADFs. As a notable example and as we suggested in the introduction, backdoor approaches that utilize the distance to subclasses with easier complexity, such as the systems cegartix [19] for AFs as well as the very recent k++ADF [24] for ADFs, can be devised on the basis of our results.

Finally, also from a theoretical perspective our work leaves open several further avenues to explore. In particular, we consider to extend our studies to other ADF semantics [22,28] as well as generalizations of ADFs [7].

## Notes

2 This construction is a slight adaption of a result from [32].

## Acknowledgements

This research has been supported by FWF projects I2854, P30168, and W1255, and by DFG project 389792660 – TRR 248. The second researcher is currently embedded in the Center of Data Science & Systems Complexity (DSSC) Doctoral Programme at the University of Groningen.

## References

 [1] L. Al-Abdulkarim, K. Atkinson and T.J.M. Bench-Capon, A methodology for designing systems to reason with legal cases using abstract dialectical frameworks, Artificial Intelligence Law 24(1) (2016), 1–49. doi:10.1007/s10506-016-9178-1. [2] P. Baroni, M. Caminada and M. Giacomin, An introduction to argumentation semantics, Knowledge Eng. Review 26(4) (2011), 365–410. doi:10.1017/S0269888911000166. [3] G. Brewka, M. Diller, G. Heissenberger, T. Linsbichler and S. Woltran, Solving advanced argumentation problems with answer-set programming, in: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI 2017), AAAI Press, 2017, pp. 1077–1083. [4] G. Brewka, S. Ellmauthaler, H. Strass, J.P. Wallner and S. Woltran, Abstract dialectical frameworks revisited, in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), IJCAI/AAAI, 2013, pp. 803–809. [5] G. Brewka, S. Ellmauthaler, H. Strass, J.P. Wallner and S. Woltran, Abstract dialectical frameworks. An overview, IfCoLog Journal of Logics and their Applications 4(8) (2017), 2263–2318. [6] G. Brewka, S. Ellmauthaler, H. Strass, J.P. Wallner and S. Woltran, Abstract dialectical frameworks: An overview, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018. [7] G. Brewka, H. Strass, J.P. Wallner and S. Woltran, Weighted abstract dialectical frameworks, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI, 2018), AAAI Press, 2018, pp. 1779–1786. [8] G. Brewka and S. Woltran, Abstract dialectical frameworks, in: Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), AAAI Press, 2010, pp. 102–111. [9] E. Cabrio and S. Villata, Abstract dialectical frameworks for text exploration, in: Proceedings of International Conference on Agents and Artificial Intelligence (ICAART 2016), SciTePress, 2016, pp. 85–95. [10] S. Coste-Marquis, C. Devred and P. Marquis, Symmetric argumentation frameworks, in: Proceedings of the 8th European Conference OnSymbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2005), Springer, 2005, pp. 317–328. doi:10.1007/11518655_28. [11] M. Diller, A. Keshavarzi Zafarghandi, T. Linsbichler and S. Woltran, Investigating subclasses of abstract dialectical frameworks, in: Proceedings of Computational Models of Argument (COMMA 2018), IOS Press, 2018, pp. 61–72. [12] M. Diller, J.P. Wallner and S. Woltran, Reasoning in abstract dialectical frameworks using quantified Boolean formulas, in: Proceedings of Computational Models of Argument (COMMA 2014), IOS Press, 2014, pp. 241–252. [13] P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2) (1995), 321–357. doi:10.1016/0004-3702(94)00041-X. [14] P.E. Dunne, Computational properties of argument systems satisfying graph-theoretic constraints, Artificial Intelligence 171(10–15) (2007), 701–729. doi:10.1016/j.artint.2007.03.006. [15] P.E. Dunne and T.J.M. Bench-Capon, Coherence in finite argument systems, Artificial Intelligence 141(1/2) (2002), 187–203. doi:10.1016/S0004-3702(02)00261-8. [16] P.E. Dunne, W. Dvorák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artificial Intelligence 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006. [17] W. Dvořák and P.E. Dunne, Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 631–687. [18] W. Dvorák, J. Fandinno and S. Woltran, On the expressive power of collective attacks, Argument & Computation 10(2) (2019), 191–230. doi:10.3233/AAC-190457. [19] W. Dvořák, M. Järvisalo, J.P. Wallner and S. Woltran, Complexity-sensitive decision procedures for abstract argumentation, Artificial Intelligence 206 (2014), 53–78. doi:10.1016/j.artint.2013.10.001. [20] W. Dvorák, S. Ordyniak and S. Szeider, Augmenting tractable fragments of abstract argumentation, Artificial Intelligence 186 (2012), 157–173. doi:10.1016/j.artint.2012.03.002. [21] G. Flouris and A. Bikakis, A comprehensive study of argumentation frameworks with sets of attacking arguments, International Journal of Approximate Reasoning 109 (2019), 55–86. doi:10.1016/j.ijar.2019.03.006. [22] S.A. Gaggl, S. Rudolph and H. Strass, On the computational complexity of naive-based semantics for abstract dialectical frameworks, in: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), IJCAI/AAAI, 2015, pp. 2985–2991. [23] A. Keshavarzi Zafarghandi, Investigating Subclasses of Abstract Dialectical Frameworks, Master’s thesis, TU Wien, 2017. [24] T. Linsbichler, M. Maratea, A. Niskanen, J.P. Wallner and S. Woltran, Novel algorithms for abstract dialectical frameworks based on complexity analysis of subclasses and SAT solving, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI 2018), Ijcai.org, 2018, pp. 1905–1911. [25] T. Linsbichler, J. Pührer and H. Strass, A uniform account of realizability in abstract argumentation, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), IOS Press, 2016, pp. 252–260. [26] D. Neugebauer, Generating defeasible knowledge bases from real-world argumentations using D-BAS, in: Proceedings of the 1st Workshop on Advances in Argumentation in Artificial Intelligence Co-Located with XVI International Conference of the Italian Association for Artificial Intelligence, CEUR-WS.org, 2017, pp. 105–110. [27] S.H. Nielsen and S. Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: Argumentation in Multi-Agent Systems (ArgMAS 2006), Springer, 2006, pp. 54–73. [28] S. Polberg, Understanding the abstract dialectical framework, in: Logics in Artificial Intelligence – 15th European Conference (JELIA 2016), Springer, 2016, pp. 430–446. doi:10.1007/978-3-319-48758-8_28. [29] J. Pührer, Realizability of three-valued semantics for abstract dialectical frameworks, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), AAAI Press, 2015, pp. 3171–3177. [30] J. Pührer, ArgueApply: A mobile app for argumentation, in: Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2017), Springer, 2017, pp. 250–262. doi:10.1007/978-3-319-61660-5_23. [31] H. Strass, Approximating operators and semantics for abstract dialectical frameworks, Artificial Intelligence 205 (2013), 39–70. doi:10.1016/j.artint.2013.09.004. [32] H. Strass, Expressiveness of two-valued semantics for abstract dialectical frameworks, Journal of Artificial Intelligence Research 54 (2015), 193–231. doi:10.1613/jair.4879. [33] H. Strass, Expressiveness of two-valued semantics for abstract dialectical frameworks, Journal of Artificial Intelligence Research 54 (2015), 193–231. doi:10.1613/jair.4879. [34] H. Strass and S. Ellmauthaler, GoDIAMOND 0.6.6 – ICCMA 2017 System Description, 2017, available at: http://argumentationcompetition.org/2017/goDIAMOND.pdf. [35] H. Strass and J.P. Wallner, Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory, Artificial Intelligence 226 (2015), 34–74. doi:10.1016/j.artint.2015.05.003. [36] J.P. Wallner, Structural constraints for dynamic operators in abstract argumentation, in: Proceedings of Computational Models of Argument (COMMA 2018), IOS Press, 2018, pp. 73–84.