Relating the Semantics of Abstract Dialectical Frameworks and Standard AFs

1 Introduction

The widely studied approach to abstract argumentation proposed by Dung [1995] uses a directed graph scheme (called an argumentation framework - AF), 〈X,A〉, in which X defines a set of atomic arguments and A a binary relation between these. In Dung's model, A is seen as capturing a concept of "incompatibility" of arguments, x and y say, in the sense that 〈x, y〉 ∈ A indicates "the argument x attacks the argument y". Recognising that interaction between arguments may involve relationships other than that of "attack", [Cayrol and Lagasquie-Schiex, 2005; Amgoud et al., 2008] introduced bipolar frameworks wherein an additional support relation, R, between arguments is specified: hence 〈x, y〉 ∈ R allows both x and y simultaneously to be accepted on the grounds that "the argument x Although it is not hard to show that standard AFs may be directly realised as ADFs with the basic stable extension semantics of the former corresponding to the so-called models of the latter, it is far from clear to what extent efficient translations in the reverse direction are possible: naive simulations in which ADF models map to AF stable extensions lead to an exponential increase in the number of arguments. The main result of this paper is to show that any ADF may be simulated (in a sense to be made precise) by an AF only polynomially larger and that this translation can be effected by a polynomial time algorithm.

∗The third author is supported by the Vienna Science and Technology Fund (WWTF) under grant ICT08-028.

We first review the basic elements of AFs and ADFs in Section 2; Section 3 recalls some supporting ideas from Boolean function complexity and its relation to AFs as these are applied in our constructions. The main results of the paper are presented in Sections 4 and 5 with discussion of these and conclusions offered in Section 6. 2

2 Background

We first recall the abstract model of argumentation presented in [Dung, 1995].

1 An alternative mechanism is implicit in [Gabbay, 2009].

2 Due to space restrictions some proofs were omitted. Proofs for results fundamental for the rest of the paper are included.

Definition 1 An argumentation framework (AF) is a pair 〈X,A〉, in which X is a finite set of arguments and A ⊆ X × X is the attack relationship. A pair 〈x, y〉 ∈ A is referred to as 'y is attacked by x' or 'x attacks y'; x ∈ X is acceptable with respect to S ⊆ X if for every y ∈ X that attacks x there is some z ∈ S that attacks y. The characteristic function, F : 2X → 2X is the mappingwhich, given S ⊆ X, reports the set of y ∈ X for which y is acceptable to S. The grounded extension is the (unique) least fixed point of F, i.e. defining F 0 = ∅, F k = F(F k-1 ) the set corresponding to the least value i with F i = F i-1 . We denote by GE(〈X , A〉) the arguments in the grounded extension of 〈X,A〉. The set S ⊆ X is conflict free if no argument in S is attacked by any other argument in S. A conflict free set S is: admissible if every y ∈ S is acceptable w.r.t S; and a stable extension if every y ̸∈ S is attacked by some x ∈ S;

The development of Dung's model which is the focus of the current paper are the Abstract Dialectical Frameworks (ADFs) from [Brewka and Woltran, 2010].

Definition 2 An abstract dialectical framework is a triple 〈S,L, C〉 with S = {s1, . . . , sm} a finite set of arguments, L ⊆ S × S a set of binary links, and C = 〈C1, C2, . . . , Cm〉 a collection of acceptance conditions described as (total) propositional functions Ci : 2par(si) → 〈⊤,⊥〉 where par(si) = {r ∈ S : 〈r, si〉 ∈ L}. A subset M of S is conflict-free if for all s ∈ M, Cs[M ∩ par(s)] = ⊤; M is a model if M is conflict-free and for each s ∈ S, Cs[M ∩ par(s)] = ⊤ implies s ∈ M, i.e. M is a model if for for each s ∈ S: s ∈ M if and only if Cs[M ∩ par(s)] = ⊤.

In Section 5 we will recall the notions of well-founded and stable models for ADFs.

We use the following notational convention: for par(s) = 〈r1, . . . , rm〉, Cs[R] with R ⊆ par(s) corresponds to the assignment αR of propositional values in 〈⊥, ⊤〉m with αi = ⊤ if and only if ri ∈ R. Similarly, for α ∈ 〈⊥,⊤〉m, Rα ⊆ par(s) contains exactly {ri : αi = ⊤}. In general, in describing evaluations of Cs, square brackets ([ ]) will be used for subsets of par(s), and parentheses - ( ) - for propositional assignments, so that Cs[R] is the same as Cs(αR) and Cs(α) corresponds to Cs[Rα].

Central to the results of Section 4 is the concept of "an AF simulating an ADF".

Definition 3 Let 〈S,L, C〉 be an ADF. The AF 〈X,A〉 simulates 〈S,L, C〉 if all of the following properties hold.

• S1. S ⊆ X.
• S2. If M ⊆ S is a model of 〈S,L, C〉 there is a subset, YM of X , for which M ∪YM is a stable extension of 〈X , A〉.
• S3. If T ⊆ X is a stable extension of 〈X,A〉 then T ∩S is a model of 〈S, L, C〉.

In informal terms, the AF HD = 〈X,A〉 simulates the ADF D = 〈S,L, C〉 if we can map models in the latter to stable extensions in the former and vice versa.

3 Boolean functions and AFs

The presentation of an ADF 〈S, L, C〉 in a computational setting must describe two components: the directed graph structure 〈S,L〉; and the set of propositional functions (acceptance conditions) prescribed by C. In considering notions of how "efficiently" an arbitrary ADF, 〈S,L, C〉, can be simulated using an AF, 〈X,A〉, we cannot assess this solely in terms of how |X| relates to |S|. Some cost is incurred in describing C and thus a more "reasonable" measure of simulation efficiency is in terms how |X| compares to the total cost of describing the set |C|. In order to formalise this we need to consider what representations for propositional functions could be used together with associated size measures. There is, of course, a wide variety of schemes that have been considered for representing propositional functions. We shall concentrate on two related methods: propositional formulae over a fixed logical basis (an approach that has been widely exploited in AI contexts); and the Boolean combinational network model (or straight-line program) which is of importance in providing a benchmark for efficient realisation. 3

Definition 4 Let Zn = 〈z1, z2, . . . , zn〉 be a set of n propositional variables. An {∧, ∨, ¬}-formula (or simply formula), ϕ(Zn), is any expression formed by a finite number of applications of the following rules:

1. ∀ z ∈ Zn, z and ¬z are formulae.
2. If ψ1 and ψ2 are formulae then (ψ1 ∨ψ2) and (ψ1 ∧ψ2) are both formulae.

The size of ϕ(Zn), denoted |ϕ(Zn)|, is one plus the total number of applications of (2) in constructing it, i.e. |z| = |¬z| = 1 and |ψ1 θ ψ2| = 1 + |ψ1| + |ψ2| (for θ ∈ {∧, ∨}).

It should be noted that we do not explicitly allow the constant values {⊤, ⊥} as formulae.

Propositional formulae (over {∧, ∨, ¬}) may be viewed as a restricted class of Boolean networks (also known as straight-line programs).

Definition 5 A Boolean network C(V,E) over the basis {∧, ∨, ¬} and inputs 〈z1, . . . , zn〉 is defined by a directed acyclic graph in which no vertex has in-degree exceeding 2. The vertices of C are either gates whose in-degree is 2; or inputs which have in-degree 0. The network C has exactly 2n input vertices each mapped to a unique member of 〈z1, ¬z1, z2, ¬z2 . . . , zn, ¬zn〉 while gates are mapped to one of the operations {∧, ∨} (when the in-degree is 2). Exactly one vertex (called the output) has out-degree 0 (note that we assume every input vertex has out-degree at least 1, otherwise the corresponding literal cannot influence the network computation). A topological sort of the vertices in a Boolean network C is a mapping τ : V → {1, 2, . . . , |V |} with the following properties:

1. The input vertex associated with zi has τ(zi) = i.
2. The input vertex associated with ¬zi has τ(zi) = n + i.
3. If w is a ∧-gate or ∨-gate vertex with 〈u,w〉 ∈ E and 〈v, w〉 ∈ E then τ (w) > max{τ (u), τ (v)}.

3 By which we mean that within the field of Boolean function complexity theory, see e.g. [Dunne, 1988], this model has a similar status to that of Turing machines in standard computational complexity theory.

It is well-known (e.g. using depth-first search) that a topological sort labelling always exists and can be constructed in O(|V | + |E|) steps. Given C(V,E) let 〈z1, . . . , zn, ¬z1, . . . , ¬zn〉 ⊂ V denote its inputs and 〈g1, g2, . . . , gm〉 its gates where C may be topologically sorted so that τ(gi) = 2n + i. Notice that gm is the unique output. A Boolean network represents the propositional function f : 〈⊤,⊥〉n → 〈⊤,⊥〉 at gm via: res(gm) = f(z1, . . . , zn) where for u ∈ V ,

The size of a Boolean network, C(V,E) with inputs 〈z1, . . . , zn〉 is the number of gate vertices in V , i.e. |V |-2n. One view of propositional formulae is as Boolean networks in which the out-degree of any gate vertex is at most 1.

4 Efficient computation of ADF models via AFs

We now present the main result of this paper: that for any ADF, 〈S,L, C〉, there is an AF, 〈X,A〉, simulating it, in the sense of Defn. 3 and for which |X| is linear in the total size of the representations used for C. Noting the view of formulae as a restricted type of Boolean network, without loss of generality, it is assumed that each acceptance condition Cs ∈ C is described by a network, Cs(Vs, Es).

The first step, presented in Lemma 1 shows that we can transform an arbitrary Boolean network into a corresponding AF. We then use this construction as the basis of the ADF simulation described in Thm. 1.

Lemma 1 Let C(V,E) be a Boolean network with inputs 〈z1, . . . , zn, ¬z1, . . . , ¬zn〉, output gate gm (so that |V | = 2n + m) and using (gate) operations from {∧, ∨}. Suppose C realises the propositional function f(z1, . . . , zn), i.e. res(gm) = f(z1, . . . , zm). There is an AF, 〈X,A〉 such that: 1) X contains arguments labelled {z1, . . . , zn, ¬z1. . . . , ¬zn, g1, . . . , gm}; 2) For every assignment α ∈ 〈⊤,⊥〉n (α = 〈α1, . . . , αn〉) and vertex v with res(v)(α) = ⊤, there is a subset Y of X \ {z1, . . . , zn, ¬z1, . . . , ¬zn} such that the set Svα given by Y ∪ {v} ∪ { zi : αi = ⊤} ∪ {¬zi : αi = ⊥} is an admissible set of 〈X , A〉. Furthermore if res(gm)(α) = f(α) = ⊤ then Sgm α is a stable extension of 〈X,A〉. 3) For any stable extension S ⊆ X the assignment αi = ⊤ if zi ∈ S; αi = ⊥ if ¬zi ∈ S is well-defined (that is, S must contain exactly one of {zi, ¬zi} for each 1 ≤ i ≤ n) and is such that gm ∈ S if and only if f(α) = ⊤. 4) |X| = 2n+O(m).

Proof: We form a sequence of AFs, {〈Xi,Ai〉}0≤i≤m with:

and 〈Xi,Ai〉 satisfies (1)-(4) wrt the sub-network of C induced by

For the inductive base we have i = 0 and there are only input vertices of C to consider.

It is easily seen that 〈X0,A0〉 already satisfies (1)-(4) (condition (3) being redundant since no gate arguments are present) as res(zi) = ⊤ if and only if zi = ⊤ (similarly res(¬zi) = ⊤ if and only if zi = ⊥).

For the inductive step, suppose we have constructed 〈Xi-1,Ai-1〉 with the desired properties. Consider, therefore gi (i ≥ 1) and the inductively defined AF, 〈Xi-1,Ai-1〉. Suppose that 〈uj , gi〉 ∈ E and 〈uk, gi〉 ∈ E. Since we are observing topological order, by the inductive hypothesis it follows that {uj , uk} ⊆ Xi-1.

Case 1: gi is an ∧-gate in C(V,E).

In this case res(gi)(α) = ⊤ if and only if res(uj)(α) = ⊤ and res(uk)(α) = ⊤. It is immediate that (1) is satisfied; furthermore (2) holds: given α with res(gi)(α) = ⊤ let Zα be given by { zi : αi = ⊤} ∪ { ¬zi : αi = ⊥}, Yj be the subset defined from the fact res(uj)(α) = ⊤ and Yk that from res(uk)(α) = ⊤. Then it can be shown that Yj ∪ Yk ∪ {gi} ∪ Zα is is conflict-free and, thus, a stable extension of 〈Xi, Ai〉: the arguments {h1i , h2i } being attacked by {uj , uk}. Condition (3) holds by considering any stable extension S of 〈Xi,Ai〉 for which gi ̸∈ S. In this case S ∩ {h1i , h2i } ̸= ∅ thus at least one of uj ̸∈ S or uk ̸∈ S holds. Let α be the assignment to 〈z1, . . . , zn〉 arising fromS: that res(gi)(α) = ⊥ follows by induction using the subset of S defining a stable extension in 〈Xj,Aj〉 (uj ̸∈ S) or 〈Xk,Ak〉 (when uk ̸∈ S).

Finally |Xi| = |Xi-1| + 3 establishing that (4) holds.

Case 2: gi is an ∨-gate in C(V,E).

From res(gi)(α) = ⊤ if and only if at least one of res(uj)(α) = ⊤ or res(uk)(α) = ⊤, a similar argument to the ∧-gate case establishes this case. □

Theorem 1 Let 〈S,L, C〉 be an ADF and assume that each acceptance condition Ci ∈ C is described using a Boolean network, (Vi,Ei) with output gate si such that res(si)(par(si)) = Ci. There is an AF, 〈X,A〉 that: simulates 〈S,L, C〉; has |X| linear in the total size of networks encoding C; and is constructible in polynomial time.

Proof: For any s ∈ S for which par(s) = ∅, we have Cs(par(s)) ∈ {⊤,⊥} and the AFs in Fig 1 are used (note that these are not dealt with in Lemma 1).

For the remaining cases, recalling that each acceptance condition, Cs, describes a propositional function of the variables par(s), first construct, for each s ∈ S an AF, 〈Xs,As〉 with the properties described in Lemma 1. In these AFs, let s be the argument (of Xs) corresponding to the output gate of (Vs,Es) and 〈r1, . . . , rt, ¬r1, . . . , ¬rt〉 be the arguments defining the inputs of (Vs,Es) (so that par(s) =

{r1, . . . , rt} in 〈S,L, C〉). It is convenient (although not essential) to add for each (non-constant) case, an additional argument to 〈Xs,As〉 which is denoted ¬s and the attacks {〈¬s, s〉, 〈s, ¬s〉}.

To complete the construction, for each 〈Xs,As〉 we identify the input arguments, i.e. 〈r1, . . . , rt, ¬r1, . . . , ¬rt〉 with the respective output arguments, i.e from 〈Xrj ,Arj 〉. The only exception is when Cr is a constant function in which case the mutual attack {〈r, ¬r〉, 〈¬r, r〉} in 〈Xs,As〉 is removed and the appropriate structure from Fig 1 used instead. Notice that one property of the construction is that an argument p corresponding to the output of (Vp, Ep) - the network encoding Cp - is never in conflict with any argument q corresponding to the output of (Vq,Eq) even when 〈p, q〉 ∈ L so that p is one of the input node of (Vq,Eq). Suppose that M ⊆ S is a model of 〈S, L, C〉. By definition, M is conflictfree and the corresponding subset SM = { s ∈ X : s ∈M} is also conflict-free in 〈X,A〉 from our earlier observations. It remains to construct a stable extension, TM in 〈X,A〉 with SM ⊆ TM. From the fact that M is a model in 〈S, L, C〉 we have s ∈ M if and only if Cs[M ∩ par(s)] = ⊤. It follows that by considering (Vs,Es) the Boolean network encoding of Cs and the inputs from M ∩ par(s), that the assignment αM∩par(s) to par(s) is such that res(gs)(αM∩par(s)) = ⊤. Thus, via Lemma 1, for every s ∈ M we find a stable extension Ys in 〈Xs,As〉. It follows, via a similar argument to that used previously, that MS ∪ ⋃s∈M Ys is a stable extension of 〈X,A〉 completing the proof of (b). For space reasons we omit the proof that if T is stable extensions of 〈X,A〉 then T ∩ S is a model. □

We conclude this section with a small illustrating example.

Example 1 Consider the ADF D given as 〈{a, b, c}, {〈a, b〉, 〈b, a〉, 〈b, c〉}, {Ca, Cb, Cc}〉, i.e.

In this Ca(b) = b, Cb(a) = a and Cc(b) = ¬b. The AF, HD adds to {a, b, c} two auxiliary arguments - za and zb - and has attack set {〈za, a〉, 〈a, zb〉, 〈zb, b〉, 〈b, za〉, 〈b, c〉}. HD has two stable extensions - {a, b} and {za, zb, c} - the former corresponding to the model {a, b} and the latter to the model {c}.

5 Grounded and stable ADF models

As we have seen, models of an ADF D can be computed efficiently by translating D into an argumentation framework HD . The stable models of the latter exactly characterize the models of D. Now, although models certainly are a fundamental notion in the ADF approach, they are not the most significant semantic notions. As for AFs, well-founded, stable and preferred semantics appear far more interesting. For this reason we extend our analysis, focusing on well-founded and stable models. 4

5.1 Well-founded models

We recall that the well-founded model of an ADF, D = 〈S,L, C〉 is defined via the operator ΓD with ΓD(A,R) = ( acc(A,R), reb(A,R) ) where acc(A,R) is {r ∈ S : A ⊆ S′ ⊆ S \ R ⇒ Cr[S′ ∩ par(r)] = ⊤} and reb(A,R) is {r ∈ S : A ⊆ S′ ⊆ S \ R ⇒ C[S′ ∩ par(r)] = ⊥]}. As shown in [Brewka and Woltran, 2010], it has a least fixed point obtained by iterating ΓD(∅, ∅). The well-founded model of D is defined as the set E ⊆ S for which there is some E′ ⊆ S having (E, E′ ) the least fixed point of ΓD.

It turns out that the AF simulating an ADF captures the wellfounded model via its grounded extension in the same way as it captures ADF models via its stable models.

Theorem 2 Let D = 〈S, L, C〉 be an ADF with well-founded model W. Let HD the AF resulting from translating D, G its grounded extension. Then we have G ∩ S = W.

5.2 Stable models: loop formulas

We first recall the definition of stable models from [Brewka and Woltran, 2010]. They are defined for bipolar ADFs (BADFs) only where each link is supporting or attacking: formally a link, (r, s) is supporting (attacking) iff there is no R ⊆ par(s) for which Cs(R) = ⊤ (resp. ⊥) but Cs(R ∪ {r}) = ⊥ (resp. ⊤).

Let D = 〈S, L, C〉 be a BADF. A model M of D is called stable if M is the least model 5 of the reduced ADF DM obtained from D by

1. eliminating all nodes not contained in M together with all links in which any of these nodes appear,
2. eliminating all attacking links,
3. replacing in each acceptance condition Cs of a node s in DM each occurrence of a statement t /∈ M with ⊥.

This definition, inspired by the definition of the same notion for logic programs [Gelfond and Lifschitz, 1991], excludes models containing self-supporting cycles, i.e., each node in a stable model is required to have independent support.

Rather than modifying the simulating AF to exclude unwanted, non-stable models, we stay at the ADF level and proceed in 2 steps as follows: we first show how an arbitrary BADF D can be translated into an ADF D∗ such that the stable models of D coincide with the models of D∗ . We then simulate D∗ using the translation described above. We thus obtain an AF HD∗ whose stable models are in one-to-one correspondence with the stable models of D.

For the construction of D∗ we will adapt a technique based on so-called loop formulas, originally proposed by Lin and Zhao [2004] for logic programming. Lin and Zhao showed that by adding adequate formulas to the Clark completion of a logic program one can obtain a propositional theory whose models are exactly the stable models of the original program.

4 Preferred models depend on the definition of stable models and thus may be considered somewhat less fundamental.

5 There is a unique such model [Brewka and Woltran, 2010].

The definition of the loop formulas required for BADFs is simplified because (1) supporting cycles can directly be "read off" the BADF graph, and (2) an explicit acceptance condition for each node, rather than a set of rules, is given.

Let D be a BADF. We call a non-empty set L = {A1, . . . ,An} of nodes in D a support loop whenever Ai,Aj ∈ L implies that Aj is reachable from Ai through a (nonempty) sequence of supporting links in D.

Let L = {A1, . . . , An} be a support loop and C1, . . . , Cn the acceptance conditions of A1, . . . ,An, respectively. The loop formula of L is the implication

Here, C ¬L i stands for the formula which is obtained by replacing in the acceptance condition Ci each occurrence of any element in L by ⊥. Intuitively, the implication says that when the nodes in L are ⊤, then there must be independent support for at least one of the nodes Ai in L. Independent support means: Ai's acceptance condition Ci is satisfied even if the predecessors of Ai in the support loop are not ⊤.

For the construction of D∗ we need to compute the loop formulas of all support loops in D. Let LF1, . . . , LFk be the (complete) collection of the loop formulas.

We must guarantee that D∗ has no model in which any of the loop formulas is violated. This can be achieved by introducing a new, self-attacking node, say F. The self-attack must become "active" whenever one of the loop formulas is violated. This can be achieved by choosing for F the following acceptance condition:

This is similar to the use of constraints in logic programming. As long as no loop formula is violated, F cannot be ⊤ and does not do any harm. However, if there is a violation, then the respective set of nodes cannot be a model, as F is missing although CF is satisfied; yet adding F also does not lead to a model, as ¬F and thus CF is then not satisfied.

Example 2 Consider the BADF given in Example 1 above. Recall links (a, b) and (b, a) are supporting (that is, Ca = b, Cb = a) and (b, c) is attacking (Cc = ¬b). The single support loop is {a, b}. Its loop formula is a∧b →⊥which is equivalent to ¬(a ∧ b). To construct D∗ we introduce a new node F with CF = a ∧ b ∧ ¬F. It is easy to verify that the single model of D∗ is exactly the single stable model of D. Now consider the extended BADF D′ :

Links (e, d) and (d, e) are attacking (Ce = ¬d, Cd = ¬e). (e, a) is an additional supporting link for a and Ca becomes e ∨ b. D′ has three models, namely M1 = {e, a, b}, M2 = {d, c} and M3 = {d, a, b}. M1 as well as M2 are stable, M3 is not.

As before, the single support loop is {a, b}. Its loop formula (after simplifications) now is a ∧ b → (e ∨ ⊥). To construct D′∗ we add a node F with CF = a ∧ b ∧ ¬e ∧ ¬F .

M1 and M2 are models of D′∗ (the acceptance condition of F is not satisfied). As intended, M3 is not a model as the self-attack of F is enforced whenever a, b are ⊤ and e is ⊥.

Theorem 3 Let D be a BADF, D∗ the ADF constructed as described above. The stable models of D are exactly the models of D∗ .

Although D∗ has only a single additional node F, the size of CF may obviously be exponential as there may be an exponential number of loops. The (indirect) translation to AD∗ thus may lead to an exponential blowup. We thus present next an alternative translation which avoids such a blowup.

5.3 Stable models: a polynomial translation

The idea here is to cope with self-supporting loops by observing that the existence of a certain order for checking the satisfaction of the acceptance excludes such self-supports. We can in fact use ADFs themselves for guessing such orders, and in case an order exists, the models of a suitably extended ADF will correspond to the stable models of the original ADF. Thus compared to the previous approach which followed the ideas of loop formulas, we generalize here another concept from logic programs, viz. level mappings as, for instance, used in [Ben-Eliyahu and Dechter, 1994].

For this purpose we need a certain ADF for guessing orders between statements S. To this end, we define the ADF

where n is the cardinality of S, S(i) = {si : s ∈ S} carries a copy si for each s ∈ S, and S< = {f} ∪ {(t < s) : s, t ∈ S, s ̸= t} provides statements (t < s) which are used to indicate an order between elements from S and f will be a "constraint" statement which ensures the order. We next describe the parts of L and C. First we have links between all si for a given i, i.e. {(si , ti ) : s, t ∈ S, s ̸= t} ⊆ L for each i. All these links are simply attacking, thus at most one si is selected for each level i in a model. In order to ensure that exactly one such si is selected and that for each i different statements are selected, we use the constraint f, i.e. we have links in L from each si to f and the acceptance condition for f is given as

Finally, for each statement (t < s) we link all si 's and ti 's to (t < s) and define as acceptance condition for (t < s):

Thus, (t < s) has to be in a model iff tj and si with j < i are in the model. We note that for given S, D< S can be constructed from S in polynomial time.

Lemma 2 Let S be a set of statements and D< S as given above. Then, (i) for each order < on S, there exists a model M of D< S such that (t < s) ∈ M ∩ S< iff t < s holds; (ii) for each model M of D< S the statements inM ∩S< describe a valid total order on S.

We are now ready to define a translation which maps an ADF D = 〈S, L, C〉 to an ADF D† such that the stable models of D are in correspondence with the models of D† . The construction of D† is as follows:

1. it contains the original ADF D;
2. it contains a certain copy D′ of D which is linked to
3. the order-guessing ADF D< S ; and
4. has a further constraint node g linked fromD and D′ .

The copy D′ = 〈S′ , L′ , C ′ 〉 is the same as D but for each supporting link (t, s) in D there is now also a link from (t < s) to s′ . Accordingly the acceptance conditions C ′s′ are obtained from Cs by replacing each occurrence of t (where (t, s) is supporting in D) by (t′ ∧ (t < s)), and all remaining occurrences of statements u (i.e. (u, s) is attacking in D) by u′ . Finally, the acceptance condition for the additional node g is:

Again, D† can be constructed from D in polynomial time.

Theorem 4 For any BADF D = 〈S, L, C〉, the stable models of D are given by {M ∩ S : M is a model of D† }.

We thus can compute stable models of D by constructing the AF HD† . Each stable model of the latter will contain a stable model of D, and each stable model of D will be contained in a model of HD† . Contrary to the loop formula approach this construction is polynomial. This comes at a cost, though: the models of HD† contain numerous nodes whose intuitive meaning is entirely technical and not interpretable in terms of the original statements in D.

6 Discussion and Conclusions

Our main aim in this paper has been to consider the relationship between the ADF model of abstract argumentation from [Brewka and Woltran, 2010] and the widely studied approach of argumentation frameworks from [Dung, 1995]. An important motivation for ADFs (as indeed had earlier been the case for bipolar AFs) concerns the restrictive view of argument interaction within AFs: in AFs arguments are related only in terms of one attacking another. Bipolar frameworks recognize that arguments may interact in other ways (e.g. through notions of support); ADFs continue and enrich the sphere of explicitly recognized interaction between arguments through their use of specified propositional acceptance conditions.

Our simulation shows that computation of ADF models is equivalent to computing the stable extensions in a related AF. For well-founded and stable models of ADFs we obtain a similar picture. The well-founded model is captured by the grounded extension of the related AF. For stable models the situation is somewhat more involved: we presented two ADF-to-ADF translations which provide a relation between stable models of an ADF and models of its translation. The translation based on loop formulas was exact yet exponential, the non-exact translation introduces numerous nodes whose meaning is entirely technical. In total the results may be interpreted as demonstrating that arbitrarily complex interactions describing the acceptability of an argument x in terms of acceptability of its parent arguments, par(x), can always be expressed in terms of attacks between arguments in an AF 〈Y ∪ {x} ∪ par(x),A〉. Of course while in principle it is sufficient to consider only "attack" as the basis for argument interaction, this will often render direct modeling of specific argumentation scenarios rather opaque: this is most apparent for stable models where users must specify arguments whose purpose is entirely technical.

In this light, noting contributions such as that of [Brewka and Gordon, 2010] in reconstructing the less abstracted and more natural expressive formalism defined by the Carneades framework of [Gordon et al., 2007], we can view our results in a much more positive light: since ADFs can be "compiled" into "equivalent" AFs with polynomial overhead, ADFs can be used as a convenient representation device but examined and analysed at the basic AF level. One issue, and the subject of current empirical study, is the extent to which the resulting AF structures have reasonable algorithmic properties.