You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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.

In this work, we aim to define several subclasses of ADFs and investigate how the restrictions we define influence the semantic evaluation of such ADFs. As a first class, we consider acyclic ADFs (i.e., the link-structure forms an acyclic graph) and show that – analogous to well-founded AFs – the main semantics, namely grounded, complete, preferred, and two-valued model/stable semantics, coincide for this class. We further investigate the concept of symmetric ADFs. In contrast to the case of AFs, we will see that properties as coherence and relatively-groundedness do not carry over and require further restrictions which leads us to the classes of acyclic support symmetric ADFs (ASSADFs) and support-free symmetric ADFs (SFSADFs). For both classes we show that they satisfy a weaker form of coherence. We also show that these two classes differ in the sense that odd-cycle free SFSADFs are coherent while odd-cycle free ASSADFs are not. As a second contribution, following the work of Dunne et al. [16], we investigate the expressiveness of our ADF subclasses in terms of signatures, i.e. the set of possible outcomes which can be achieved by ADFs (of a particular class) under the different semantics. We thus complement here results which have been obtained for general [29,32] and bipolar ADFs [25] and also compare our ADF subclasses to abstract argumentation frameworks in terms of expressibility.

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

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.

The SETAF of example 1.

2.2.Abstract dialectical frameworks

We now proceed to define ADFs:

Definition 5

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.

Let D=(S,L,C) be an ADF. A link (b,a)L is called

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

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

The ADF of example 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={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.

3.Properties of ADF subclasses

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.

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.

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.

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.

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.

An ADF D is called

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

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.

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

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.

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.

Theorem 5.

Every acyclic support symmetric ADF (ASSADF) is weakly coherent.

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.

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

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={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

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.

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:

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.

By Theorem 5, every ASSADF is weakly coherent, and since each SFSADF is an ASSADF, also SFSADFs are weakly coherent.

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.

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.

Theorem 9.

The ADF associated to a given symmetric SETAF is a SFSADF.

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.

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.

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.

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.

4.Expressiveness of ADF subclasses

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.

Theorem 21.

For σ{adm,prf,com,mod} it holds that ΣASSADFσΣBADFσ.

Proof.

Since every ASSADF is, by definition, a BADF, ΣASSADFσΣBADFσ is clear. To show that ΣBADFσ is a strict superset of ΣASSADFσ it is enough to find an interpretation-set V which is σ-realizable in BADFs, but not σ-realizable in ASSADFs, for σ{adm,prf,com,mod}.

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.

Theorem 22.

For σ{adm,prf,com}, it holds that ΣSFSADFσΣASSADFσ.

Proof.

Since each support-free symmetric ADF is an acyclic support symmetric ADF, it is clear that ΣSFSADFσΣASSADFσ. To show that ΣASSADFσ is a strict superset of ΣSFSADFσ, for σ{adm,prf,com}, we give an interpretation-set V, which is σ-realizable in ASSADFs, but not σ-realizable in SFSADFs.

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

Thus, V is not σ-realizable in SFSADFs under σ{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.

Theorem 23.

For σ{adm,prf,com}, it holds that ΣAFσΣSFSADFσ and ΣAFσΣASSADFσ.

Proof.

To obtain our theorem we show that ΣAFσΣASSADFσ and ΣSFSADFσΣAFσ. Since, via Theorem 22, ΣASSADFσ is a strict superset of ΣSFSADFσ for σ{adm,prf,com}, we can then conclude that ΣAFσΣSFSADFσ and ΣASSADFσΣAFσ.

∙ 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 σ.

∙ To verify that ΣSFSADFσΣAFσ for σ{adm,prf,com} we first show that ΣSFSADFprfΣAFprf. Let V={v1,v2,v3} with v1={af,bt,ct,et}, v2={at,bf,ct,ef}, and v3={at,bt,cf,ef}. A witness of prf-realizability of V in SFSADFs is D=(S,L,C) with S={a,b,c,e}, φa=¬e(¬b¬c), φb=¬a¬c, φc=¬a¬b, and φe=¬a. However, there is no AF with V as its preferred interpretations. If there is an AF F such that σ(F)=V then the structure of v1, v2 and v3 implies that there is no attack between a, b and c in F. Thus, if there is an attack from any of a, b and c to e then {at,bt,ct,ef} is a preferred interpretation of F. If there is no attack from any of a, b and c to e then {at,bt,ct,et} is a preferred interpretation of F. In both cases σ(F)V. For σ=com let V=V{{au,bu,cu,eu}}. It is easy to check that V is com-realizable by the SFSADF D defined above. If there is an AF F that realizes V under com then each of the elements of V would be a preferred interpretation of F. Thus, prf(F)=V would be the case, which it is easy to see is actually false. Finally, we get ΣSFSADFadmΣAFadm by observing that from adm(D) being realizable under adm in AFs it would follow that prf(D) is realizable under prf in AFs. But we already showed that the latter is not the case. □

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.

Theorem 24.

For σ{prf,adm,com}, the following hold:

  • ΣSFSADFσΣSFADFσ,

  • ΣSFADFσΣASSADFσ,

  • ΣAFσΣSFADFσ,

  • ΣSFADFσΣBADFσ.

Proof.

We separately prove the four relations provided in the theorem.

  • Each SFSADF is a SFADF, that is, ΣSFSADFσΣSFADFσ. To show that ΣSFADFσΣSFSADFσ, let V={{au}}. A witness of σ-realizability of V in SFADFs is D=({a},{φa=¬a}}), for σ{prf,adm,com}. In contrast VΣSFSADFσ.

  • To show ΣSFADFσΣASSADFσ, let V={{au}}, which is σ-realizable in SFADFs but not in ASSADFs. To show ΣASSADFσΣSFADFσ, let V={{au,bu}}. V can be realized by D=({a,b},{φa=¬b,φb=a}) in ASSADF under σ but not in SFADF.

  • Σ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σ. □

Our results comparing the expressivity of ASSADFs, SFSADFs, SFADFs, AFs, BADFs, and general ADFs w.r.t. the admissible, complete, and preferred semantics is summarised in Fig. 9. To complete the picture here we also incorporate results about the relative expressivity of AFs, BADFs, and general ADFs from [25].

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.

Fig. 9.

Expressiveness of subclasses of ADFs for σ{adm,prf,com}.

Expressiveness of subclasses of ADFs for σ∈{adm,prf,com}.
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.

Theorem 26.

ΣAFstbΣSFSADFstbΣSFADFstbΣASSADFstbΣBADFstb.

Proof.

ΣAFstbΣBADFstb is shown in [32], and ΣSFSADFσΣASSADFσΣBADFσ and ΣSFSADFσΣSFADFσΣBADFσ, for each semantics σ, are clear. If we can show ΣBADFstbΣSFSADFstb we are thus done. Let VΣBADFstb. Since V is a set of incomparable two-valued interpretations, by Lemma 25, V is stb-realizable in SFSADFs. □

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

Theorem 28.

ΣAFmodΣSFSADFmodΣSFADFmodΣASSADFmodΣBADFmod.

Proof.

We first argue that ΣFmod=ΣFstb for F{SFSADF,SFADF,ASSADF}. This follows immediately for F{SFSADF,ASSADF} since both ASSADFs and SFSADFs are weakly coherent (cf. Theorem 5 and Theorem 8). To show the relation for F=SFADF we need to show ΣSFADFmodΣSFADFstb (the other inclusion follows by standard properties of semantics). Let VΣSFADFmod. By Lemma 27, V is incomparable and by Lemma 25, any incomparable set of two-valued interpretations is stb-realizable in SFSADF. Therefore, there is a SFSADF D such that stb(D)=V. Since each SFSADF is also an SFADF, VΣSFADFstb.

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.

Expressiveness AFs, SFSADFs, SFADFs, ASSADFs, BADFs, ADFs for σ{stb,mod}.

Expressiveness AFs, SFSADFs, SFADFs, ASSADFs, BADFs, ADFs for σ∈{stb,mod}.

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.

As a further contribution and also following in the footsteps of work for AFs [16], we considered the subclasses of ADFs we introduced (ASSADFs, SFADFs, and SFSADFs) in terms of their expressivity as can be gleaned from their signatures. Here SFSADFs are a strict subset of ASSADFs for the admissibility-based semantics we considered, while SFADFs are incomparable w.r.t. ASSADFs (and a strict superset of SFSADFs). On the other hand the signatures of ASSADFs, SFADFs, and SFSADFs coincide for the model and stable semantics.

We also complemented previous work on expressivity of AFs and ADFs [25,29,33] by comparing the expressivity of ASSADFs, SFADFs, and SFSADFs with that of AFs, bipolar ADFs (BADFs), and ADFs. Here ASSADFs and SFSADFs are incomparable with AFs for the admissibility semantics, while SFADFs are strictly more expressive. ASSADFs, SFADFs, and SFSADFs are strictly more expressive for the model and stable semantics. On the other hand, they are strictly less expressive than BADFs for the model and admissibility based semantics, while they coincide in expressivity with BADFs and general ADFs for the stable semantics.

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.