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.
Since the landmark paper by Dung  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.11
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 . 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  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  and AFs under other graph-driven restrictions . 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  that utilize the distance to an easier fragment. This approach has, for instance, been realised in practice with the cegartix system .
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 . 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  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. , 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  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)  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 . 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.
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
An abstract argumentation framework (AF) is a pair in which A is a set of arguments and is a binary relation representing attacks among arguments.
Let be an AF. When used for modelling purposes it is usually assumed that the set of arguments A is finite. Also, for each , the relation is used to represent that a is an argument attacking the argument b. We can then also say that an argument is attacked by a set if there is a that attacks b. An argument is, on the other hand, defended by a set of arguments (alternatively, the argument is acceptable with respect to S) (in F) if for each argument , it holds that if then there is a such that . In addition, a subset S of A is called conflict-free in F, if it does not attack itself. I.e. there are no such that .
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 is via the so called characteristic operator : 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 . We compile the definitions of some of the main semantics of AFs given in terms of the characteristic operator in the following:
Let be an AF. A set S which is conflict-free in F is:
admissible in F iff ;
complete in F iff ;
grounded in F iff S is the ⊆-least fixed-point of ;
preferred in F iff S is ⊆-maximal admissible (resp. complete) in F;
a stable model of F iff for all , S attacks a.
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 .
A set argumentation framework (SETAF) is an ordered pair , where A is a finite set of arguments and is the attack relation.
Given a SETAF , we write if there is a set attacking b, i.e. . We say that in this case also S attacks b. Moreover, we write if for some . We drop the subscript in 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 , a set is conflicting in F if ; is conflict-free in F, if S is not conflicting in F, i.e. if for each . An argument is defended (in F) by a set if for each , such that , also . A set T of arguments is hence defended (in F) by S if each 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 , ; 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):
Let be a SETAF. A set S which is conflict-free in F is
admissible in F iff ;
complete in F iff ;
grounded in F iff S is the ⊆-least fixed-point of ;
preferred in F iff S is ⊆-maximal admissible (resp. complete) in F;
a stable model of F iff for all , 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.
The SETAF is depicted in Fig. 1. In F, says that there is a joint attack from a and b to c, and 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 , the admissible extensions , the complete extensions , the unique grounded extension , and the preferred extensions . Note that, for instance, is a conflict-free extension. However, it is not an admissible extension, since . Further, is an admissible and a complete extension, since . On the other hand is not a preferred extension because it is not a ⊆-maximal admissible extension.
2.2.Abstract dialectical frameworks
We now proceed to define ADFs:
An abstract dialectical framework (ADF) is a tuple where;
S is a finite set of nodes (arguments, statements, positions),
is a set of links,
is a collection of propositional formulas (acceptance conditions).
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 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. . The truth values stand for different degrees of acceptance that can be associated to the arguments. The sets , , and 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. . At the other extreme, an interpretation v is called trivial, denoted , if for each . Also, we denote the update of an interpretation v with a truth value for an argument b by , i.e. and for .
Let be the set of all interpretations for an ADF D as before. Then, we call a subset of all interpretations of the ADF, , 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 and . An interpretation v is at least as informative as another interpretation w, denoted by , if for each . As usual whenever but it is not the case that . The meet operator on truth values is defined as , and returns u otherwise. The meet of two interpretations v and w is then defined as for each . The partially ordered set forms a meet-semilattice with the meet operator .
Semantics for ADFs can also be defined via a characteristic operator 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 for D is defined as
The semantics for ADFs, as defined via the characteristic operator, are provided next in Definition 6. The definitions have been introduced in [4,8]; we refer to  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).
Given an ADF , an interpretation v is
conflict-free in D iff implies is satisfiable and implies is unsatisfiable;
admissible in D iff ;
complete in D iff ;
grounded in D iff v is the least fixed-point of ;
preferred in D iff v is -maximal admissible (resp. complete) in D;
a (two-valued) model of D iff v is two-valued and for all , it holds that ;
a stable model of D if v is a model of D and , where w is the grounded interpretation of the -reduct , where , , and for each .
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.
Let be an ADF. A link is called
supporting (in D) if for every two-valued interpretation v, implies ;
attacking (in D) if for every two-valued interpretation v, implies ;
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 . 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.
An example of an ADF 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 , states that c can be accepted in an interpretation where either a or b (or both) are rejected. The acceptance condition states that a always has to be rejected. The acceptance condition 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.
Since in ADFs an argument appears in the acceptance condition of an argument a if and only if it belongs to the set , 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 , . Moreover, given that for every two-valued interpretation v, implies , the link is supporting (in D). Further, D is a bipolar ADF in which is the set of all supporting links, and is the set of all attacking links.
In D the interpretation is conflict-free. However, v is not an admissible interpretation, because , that is, . The interpretation on the other hand is an admissible interpretation and, in fact, also the unique grounded interpretation of D. Further, , but only the first interpretation in this set is a stable model. This is because for the unique grounded interpretation w of is and . The interpretation is not a stable model, since the unique grounded interpretation of is and . In addition, we have that for the ADF D, .
As to the relationship between ADFs and AFs, an ADF is AF-like if the acceptance condition of every argument is of the form (by the usual conventions, we thus have that if , then ). Such an ADF can be represented as an AF, as a tuple with arguments and attacks . In turn, each AF can be represented as an ADF via the following definition.
Let be an AF. The associated ADF of F is in which , , and the acceptance condition of each in C is given as .
It is shown in [4,8] that the semantics of AFs and associated ADFs coincide. Also note that the associated ADF 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 is, on the other hand, SETAF-like if the acceptance condition of every argument 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  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.
Let be a SETAF. The ADF associated to F is a tuple in which, , and is the collection of acceptance conditions defined, for each , as
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 , 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.
An ADF is acyclic if its corresponding directed graph 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.
In every acyclic ADF D the -least fixed point of is a model of D.
Let be an acyclic ADF and let m be its maximum level. Moreover, let and for . We claim that for all i with , and every argument with level it holds that either or . We show this claim by induction on i:
Base case: Suppose is an arbitrary argument of level one (an acyclic ADF always includes an initial argument). Since is an initial argument, either or . Hence is either true or false.
Inductive step: Assuming this property holds for all k with , we show it holds for . We know that . For all that occur in it holds that , with k being the level of . Therefore, by the inductive hypothesis, for each , either or . Hence either or and, consequently, either or .
Since m is the maximum level of any argument in D, we now get that is either true or false for all , i.e. it is a two-valued interpretation. Moreover, it holds that , i.e. is a fixed point.
To show that is the least fixed point of , assume, towards a contradiction, that there exists an interpretation such that . Then there exists an argument s such that either or , but . Assume s has level i. Since D is an acyclic ADF all arguments that occur in have a level less than i. Therefore, there exists at least an argument of level in such that . By iterating this method after at most times we reach an argument of level 1 for which . This is a contradiction, since at level 1 all arguments are initial, it must be the case that either or , and therefore . Thus, interpretation is the least fixed point of . □
In every acyclic ADF D the sets of grounded interpretations, complete interpretations, preferred interpretations, two-valued models, and stable models coincide.
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 in which , v is a stable model. It remains to show that there is no further complete interpretation of D. Since v is two-valued it must hold that . However, since v is grounded and therefore the least complete interpretation, such a 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.
Consider the ADF . This ADF possesses the unique complete interpretation , 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 . Since both the two-valued and stable model semantics for ADFs are proper generalisations of the stable semantics for AFs , 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.
An ADF 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 , take any link such that and do the following: add to L and change the acceptance condition to . 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.
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.
An ADF D is called relatively grounded if .
In what follows, we occasionally say that a class 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.
The class of symmetric ADFs is neither semi-coherent, nor weakly coherent, nor relatively grounded.
Let D be the symmetric ADF depicted in Fig. 3. It holds that with and . Since is a two-valued model of D which is not stable (since and ), D is not weakly coherent. Also, D is not semi-coherent since is not two-valued. In addition, , but . Therefore, D is not 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.
Given an ADF , let 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 is acyclic.
The method of determining whether a given ADF is an ASSADF is clarified in Example 4.
We now show that ASSADFs are weakly coherent, using the following technical lemma.
Let D be an ADF, v a two-valued model of D, and an argument such that all parents of s are attackers. If is irrefutable then is irrefutable.
Every acyclic support symmetric ADF (ASSADF) is weakly coherent.
Let 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, be the -reduct of D, w be the unique grounded interpretation of , and the acceptance condition of s in , i.e. . We show that . Suppose to the contrary that there exists an argument s, such that and . That is, is not irrefutable. This means, by Lemma 4, that contains an argument supporting s such that , otherwise cannot be irrefutable. Thus, also contains . Since supports are acyclic in ASSADFs, for the same reasons contains an argument which is different from s and and which supports . Thus there exists an infinite sequence of arguments such that supports . 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.
The class of ASSADFs is neither semi-coherent nor relatively grounded.
Consider the ASSADF D depicted in Fig. 5. D has 4 preferred interpretations, namely , , , and . As every two-valued interpretation of D (that is , and ) is also a stable model, D is weakly coherent, confirming Theorem 5. However, is a preferred interpretation which is not a two-valued model. Hence, D is not semi-coherent.
We show now that ASSADFs are not relatively grounded in general. Consider the ASSADF , depicted in Fig. 6. Here . D has the preferred interpretations and . We obtain . However, the grounded interpretation of D is the trivial interpretation . 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.
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  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:
Given an ADF , let be the set of all attacking links in D. A bipolar ADF is a support free symmetric ADF (SFSADF for short) if it is symmetric and does not have any supporting links, that is, .
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.
Let D be an SFSADF with no isolated argument. The unique grounded interpretation of D is the trivial interpretation, .
We show that for any SFSADF with no isolated argument, . Let s be an argument. Let be an interpretation in which all parents of s are assigned to t and let be an interpretation in which all are assigned to f. Since D is an SFSADF, the former interpretation shows that is not irrefutable and the latter interpretation says that is not unsatisfiable. Therefore, for each argument s, . □
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.
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 . 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. □
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.
A SETAF , in which , is a symmetric SETAF if the following properties hold:
for all and for all , there exists such that ,
for each argument s and for each , the set S does not include s,
for each there is no with .
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.
The ADF associated to a given symmetric SETAF is a SFSADF.
Let be a symmetric SETAF. We show that the ADF associated to F is a SFSADF. By Definition 9, does not contain any supporting link. It remains to show that 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 such that . Since F is a symmetric SETAF, there is a such that . 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.
Let be a SETAF and let a be an argument on which there is no attack in F, that is, there is no . By Definition 9, in the ADF corresponding to the SETAF F the acceptance condition of a has the form . On the other hand, if there exists , it holds that . These facts together with Theorem 9 lead to the following corollary.
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 , 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.
Let be a SFSADF and let 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.
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 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 as a positive literal. Let be the set of all clauses in which t occurs (). Also, let v be a two-valued interpretation which assigns the truth value f to t; all other arguments in each is assigned to t. Also v assigns f to all other arguments of , which means that . However, . Thus, by the definition of attacking links, 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.
Let be a SFSADF in which there is no argument having an unsatisfiable acceptance condition. D can be written as a SETAF such that and R is as follows. Let be in CNF having only negative literals, let c be a clause of and let be the set of all arguments in the clause c. Then, represents a joint attack to a. The set is the set of all joint attacks to an argument a. Let , be the set of all joint attacks in . We call the SETAF associated to D.
Let be a SFSADF in which the acceptance condition of none of the arguments is unsatisfiable. The SETAF associated to D is a symmetric SETAF.
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 . It remains to show that is a symmetric SETAF. Towards a contradiction, assume that is not symmetric. Then, there are two possibilities to consider:
There exists and there exists such that for all , 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 such that . That is, t appears in the acceptance condition of t in D. That is, L in D contains a reflexive link.
The SFSADF , depicted in Fig. 7, corresponds to the symmetric SETAF with ) 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 and .
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 and the set of all possible interpretations of F are denoted by . The function , in Definition 18, is a modification of the function (associating labellings to extensions) given in Definition 5.1. of .
Let be a SETAF, and let e be an extension of F (). The truth value assigned to each argument by the three-valued interpretation associated to e is given by the function as follows.
An ADF interpretation, on the other hand, can be represented as an extension via the following mapping.
Let be an ADF and v an interpretation of D, that is, . The associated extension of v is obtained via application of the function on v, as follows:
The two subsequent lemmas are adopted from .
Let F be a SETAF, and . Moreover, let be the ADF associated to F. Then, .
Let D be a SFSADF in which the acceptance condition of none of the arguments is unsatisfiable, and the SETAF associated to D. Then, .
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 usually do not cover all admissible interpretations of the ADF . This is illustrated next.
Let be a SETAF. By Definition 9, the associated ADF to F is . It is clear that . Applying of Definition 18 to e leads to the three-valued interpretation . However, is also an admissible interpretation of which is not obtained from any admissible extension e of F via .
One can overcome this problem by mapping each admissible set e of a SETAF to several interpretations in a way that yields either u or f in case there exists such that , and for all with and there exists such that . That is, 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.
Let F be a symmetric SETAF with no isolated argument. The unique grounded extension of F is the empty set.
Let be a symmetric SETAF with no isolated argument, and let 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 . First, we show that does not contain any isolated argument. To this end, let b be an argument. Since F does not contain any isolated argument, there exists such that . The associated acceptance condition of b in , namely shows that in . Thus, the associated does not contain any isolated argument, as well. By Lemma 13 and Definition 18, a is assigned to t in . Further by Theorem 9, 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.
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.
The class of symmetric SETAFs is neither coherent nor relatively grounded.
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 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, and . Towards a contradiction, suppose . It follows that there is an interpretation with , such that , and hence . Hence, either or . In the first case and hence u cannot be preferred; in the second case 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 . Corollary 16 immediately implies that this SETAF cannot be relatively grounded. □
3.4.The role of odd-length cycles
In  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 . The interpretation 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.
The subclass of ASSADFs not containing any odd-length cycle is not coherent.
Consider the ADF . D is an ASSADF in which there is no odd cycle. The unique preferred interpretation of D is , 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.
The class of SFSADFs that do not contain any odd-length cycle is coherent.
Let 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. . Since each two-valued model is a preferred interpretation of ADFs, it is trivial that . Thus, it is enough to show that . 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 .
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 and . Assign all arguments in to t, and all arguments of to f. Construct the interpretation as follows.
It is clear that . We now show that is a two-valued model. First, there is no argument in assigned to u. To show that is a two-valued model it remains to show that . Assume that a is assigned to t in , we show that . (The method for proving the case that a is assigned to f is analogous.) If in either or .
If , since v is a preferred interpretation, . In addition, the characteristic operator is a monotonic operator, that is, .
If , then . Let be in CNF, this is possible by Lemma 11.Thus, if , then .
∗ If , then there exists a clause c in all arguments of which are assigned to t in . By the construction of , . Therefore, all arguments of c are assigned to t in v (note that all arguments in are assigned to f by the definition of ). That is, , which is a contradiction with the assumption that . Thus, .
∗ If , then there exists a parent of a the truth value of which is not indicated in . This is also a contradiction, since all parents of a are either in that are assigned to f in or assigned to by v. Therefore, .
Therefore, is a two-valued model of D and hence a preferred interpretation of D. Moreover , 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.
Given an ADF , let be the set of all attacking links in D. A bipolar ADF is called a support-free ADF (SFADF) if it does not have any supporting links, that is, .
SFADFs and SETAFs without odd-length cycles are coherent.
4.Expressiveness of ADF subclasses
Following the work of  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  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.
Let be a formalism (e.g. AFs or (subclasses of) ADFs), i.e. the set of structures available in (e.g. all possible AFs and ADFs) and σ a semantics for . Moreover, let be an interpretation-set or extension-set. is said to be σ-realizable in , if there exists an element (“knowledge base”) of such that .
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.
The signature of a formalism w.r.t. a semantics σ is defined as:
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.
For it holds that .
Since every ASSADF is, by definition, a BADF, is clear. To show that is a strict superset of it is enough to find an interpretation-set which is σ-realizable in BADFs, but not σ-realizable in ASSADFs, for .
For , let , and for , let . The BADF with and realizes under σ and under . On the other hand, it is easy to check that there is no ASSADF with one argument which realizes under σ, and respectively, under . To complete the proof toward a contradiction assume that there exists an ASSADF such that and . Since contains an assignment to only one argument, has to have just one argument. Since is an ASSADF, the argument a is an isolated argument in . That is, either or . Thus, it can realize neither under σ nor 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.
For , it holds that .
Since each support-free symmetric ADF is an acyclic support symmetric ADF, it is clear that . To show that is a strict superset of , for , we give an interpretation-set , which is σ-realizable in ASSADFs, but not σ-realizable in SFSADFs.
Let . The ASSADF with , , and realizes under . However, it is easy to check that there is no SFSADF that can realize . Assume to the contrary that there exists a SFSADF that can realize under σ, for . The set of arguments of is as these are the only ones appearing in the σ interpretations of .
If any of the arguments of is an isolated argument, then its acceptance condition is either equivalent to ⊤ or ⊥. That is, . Thus, none of the arguments could be an isolated argument in .
If there is a symmetric attack relation between a and b, then the interpretation is a preferred interpretation of and therefore it is a complete and admissible interpretation of . Therefore, , for .
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.
For , it holds that and .
To obtain our theorem we show that and . Since, via Theorem 22, is a strict superset of for , we can then conclude that and .
∙ To show consider . A witness of σ-realizability in AFs is . However, there is no ASSADF to realize under σ.
∙ To verify that for we first show that . Let with , , and . A witness of -realizability of in SFSADFs is with , , , , and . However, there is no AF with as its preferred interpretations. If there is an AF such that then the structure of , and implies that there is no attack between a, b and c in . Thus, if there is an attack from any of a, b and c to e then is a preferred interpretation of . If there is no attack from any of a, b and c to e then is a preferred interpretation of . In both cases . For let . It is easy to check that is -realizable by the SFSADF D defined above. If there is an AF that realizes under then each of the elements of would be a preferred interpretation of . Thus, would be the case, which it is easy to see is actually false. Finally, we get by observing that from being realizable under in AFs it would follow that is realizable under 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.
For , the following hold:
We separately prove the four relations provided in the theorem.
Each SFSADF is a SFADF, that is, . To show that , let . A witness of σ-realizability of in SFADFs is ), for . In contrast .
To show , let , which is σ-realizable in SFADFs but not in ASSADFs. To show , let . can be realized by in ASSADF under σ but not in SFADF.
is clear. To show that , let for , and respectively let for . Both interpretation-sets are realizable by in SFADF under σ. In contrast .
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 . □
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 .
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. implies , see . Now, in order to complete previous results from  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 .
Any incomparable set of two-valued interpretations is -realizable in SFSADFs.
(sketch) To show that any incomparable set of two-valued interpretations is -realizable by some SFSADF, let be an incomparable set over arguments S (that is, each assigns t or f to every ) and consider a SFSADF with the following acceptance conditions for :22
If for every then .
If for every then .
By the definition of the acceptance condition of argument s in D, . Therefore, L is irreflexive. Further, iff , that is, L is symmetric. In addition, all links in D are attacking. Thus, D is a SFSADF.
To prove that , we show that and also .
∗ To show , let . We show that and since SFSADFs are weakly coherent by Theorem 8, . Let , we show that s is acceptable in v. (The proof for the case that is analogous). If s is assigned t by each element of there is nothing to prove. Otherwise, there exists a s.t. . Since is incomparable, there exists t such that and . Therefore, . The set of all arguments like t make a conjunctive clause of which guarantees that s is accepted in v.
∗ To show that , toward a contradiction, assume that there exists such that . Since is incomparable, there exists such that and . Further, the acceptance condition of s is not unsatisfiable, otherwise s has to be assigned to f in v. Thus, there exists in which s is assigned to t. Let K be the set of all in which s is assigned to t. Since and is incomparable, in each there exists t such that and . Let T be a set of all arguments like t. It can be shown that either each conjunctive clause of contains a , or there exists a such that each conjunctive clause of 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 such that . Therefore, . □
Note that the incomparability condition for the set of two valued interpretations in the statement of Lemma 25 is necessary. For instance, is a set of two-valued interpretations, which are not incomparable, that is not -realizable in SFSADFs.
is shown in , and and , for each semantics σ, are clear. If we can show we are thus done. Let . Since is a set of incomparable two-valued interpretations, by Lemma 25, is -realizable in SFSADFs. □
In Example 6 we give an example of an interpretation-set that is -realizable in SFSADFs but not -realizable in AFs.
Let be an interpretation-set. A witness of -realizability of in SFSADFs is for which and the acceptance conditions are , and . We show that is not -realizable in AFs. Towards a contradiction assume that there exists an AF such that . The set of arguments of F is S as these are the arguments occurring in . The interpretations in 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 is also a stable interpretation of F. Therefore, . Thus, the interpretation-set is not -realizable in AFs and
The final semantics to investigate is the model-semantics. We only need one technical lemma.
For any SFADF , is incomparable.
Toward a contradiction assume that there are such that . Let 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, . Assume . Since D is a SFADF, all links are attacking. Then, by the definition of attacking links . That is, a is denied with respect to . Following the same method construct , for . It is obvious that a is denied in each , in particular, a is denied in , which is equal to w. This is a contradiction to the assumption that a is accepted in w. Therefore, is a set of incomparable interpretations. □
We first argue that for . This follows immediately for since both ASSADFs and SFSADFs are weakly coherent (cf. Theorem 5 and Theorem 8). To show the relation for we need to show (the other inclusion follows by standard properties of semantics). Let . By Lemma 27, is incomparable and by Lemma 25, any incomparable set of two-valued interpretations is -realizable in SFSADF. Therefore, there is a SFSADF such that . Since each SFSADF is also an SFADF, .
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  ( and ).
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.
Suppose that and is -realizable in ADFs. Then is -realizable in AFs.
Let be a set of interpretations that is -realizable in ADFs, i.e. there exists an ADF such that . Construct an AF by setting and . To prove that , take . First, there is no attack between arguments with . Moreover, if then, since neither nor , there must be some with and , hence . Therefore is a stable interpretation of F. That is, is -realizable in AFs. □
Motivated by crucial results on the semantic properties of acyclic (or well founded) , symmetric , and odd-length-cycle-free  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 . 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 , 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 . There we had also included results on an empirical evaluation of some of the main systems for ADFs (QADF , YADF , and goDIAMOND ) 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  for AFs as well as the very recent k++ADF  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 .
2 This construction is a slight adaption of a result from .
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.
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.
P. Baroni, M. Caminada and M. Giacomin, An introduction to argumentation semantics, Knowledge Eng. Review 26: (4) ((2011) ), 365–410. doi:10.1017/S0269888911000166.
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.
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.
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.
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) .
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
A. Keshavarzi Zafarghandi, Investigating Subclasses of Abstract Dialectical Frameworks, Master’s thesis, TU Wien, 2017.
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.
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.
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.
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.
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.
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.
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.
H. Strass, Approximating operators and semantics for abstract dialectical frameworks, Artificial Intelligence 205: ((2013) ), 39–70. doi:10.1016/j.artint.2013.09.004.
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.
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.
H. Strass and S. Ellmauthaler, GoDIAMOND 0.6.6 – ICCMA 2017 System Description, (2017) , available at: http://argumentationcompetition.org/2017/goDIAMOND.pdf.
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.
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.