=Paper=
{{Paper
|id=Vol-2052/paper4
|storemode=property
|title=Valid Attacks in Argumentation Frameworks with Recursive Attacks
|pdfUrl=https://ceur-ws.org/Vol-2052/paper4.pdf
|volume=Vol-2052
|authors=Claudette Cayrol,Jorge Fandinno,Luis Fariñas del Cerro,Marie-Christine Lagasquie-Schiex
|dblpUrl=https://dblp.org/rec/conf/commonsense/CayrolFCL17
}}
==Valid Attacks in Argumentation Frameworks with Recursive Attacks==
https://ceur-ws.org/Vol-2052/paper4.pdf
Valid attacks in Argumentation Frameworks with Recursive Attacks
C. Cayrol, J. Fandinno∗ , L. Fariñas del Cerro, M-C. Lagasquie-Schiex
IRIT, Université de Toulouse, CNRS, Toulouse, France
{ccayrol, jorge.fandinno, luis, lagasq}@irit.fr
Abstract prosecutor says that the defendant threw a sharp knife
towards the victim (Argument a). So, there is an at-
The purpose of this work is to study a gen- tack from a to b. And the intention to kill should be
eralisation of Dung’s abstract argumentation inferred. Then the lawyer says that the defendant was in
frameworks that allows representing recursive a habit of throwing the knife at his wife’s foot once drunk.
attacks, that is, a class of attacks whose targets This latter argument (Argument c) is better considered
are other attacks. We do this by developing a attacking the attack from a to b, than argument a itself.
theory of argumentation where the classic role Now the prosecutor’s argumentation seems no longer suf-
of attacks in defeating arguments is replaced by ficient for proving the intention to kill. This example is
a subset of them, which is extension dependent represented as a recursive framework in Fig. 1.
and which, intuitively, represents a set of “valid
attacks” with respect to the extension. The a b
studied theory displays a conservative generali-
sation of Dung’s semantics (complete, preferred
and stable) and also of its principles (conflict- c
freeness, acceptability and admissibility). Fur-
thermore, despite its conceptual differences, we Figure 1: An acyclic recursive framework
are also able to show that our theory agrees
with the AFRA interpretation of recursive at-
tacks for the complete, preferred and stable se- Another example, borrowed from [4; 9], will be taken
mantics. as a running example.
Example 2. Suppose Bob is making decisions about
1 Introduction his Christmas holidays, and is willing to buy cheap last
minute offers. He knows there are deals for travelling to
Argumentation has become an essential paradigm for Gstaad (g) or Cuba (c). Suppose that Bob has a prefer-
Knowledge Representation and, especially, for reasoning ence for skiing (p) and knows that Gstaad is a renowned
from contradictory information [1; 11] and for formaliz- ski resort. However, the weather service reports that it
ing the exchange of arguments between agents in, e.g., has not snowed in Gstaad (n). So it might not be pos-
negotiation [2]. Formal abstract frameworks have greatly sible to ski there. Suppose finally that Bob is informed
eased the modelling and study of argumentation. For that the ski resort in Gstaad has a good amount of artifi-
instance, a Dung’s argumentation framework (AF) [11] cial snow, that makes it anyway possible to ski there (a).
consists of a collection of arguments interacting with The different attacks are represented on Fig. 2.
each other through an attack relation, enabling to deter-
mine “acceptable” sets of arguments called extensions. A semantics for these classes of recursive frameworks
A natural generalisation of Dung’s argumentation has been first introduced in [14] in the context of prefer-
frameworks consists in allowing high-order attacks that ences in argumentation frameworks, and latter studied
target other attacks. Here is an example in the legal in [4] under the name of AFRA (Argumentation Frame-
field, borrowed from [3]. work with Recursive Attacks). This version describes
abstract argumentation frameworks in which the inter-
Example 1. The lawyer says that the defendant did actions can be either attacks between arguments or at-
not have intention to kill the victim (Argument b). The tacks from an argument to another attack. A transla-
∗
The second author is funded by the Centre Interna- tion of an AFRA into an AF is defined by the addition
tional de Mathématiques et d’Informatique de Toulouse of some new arguments and the attacks they produce or
(CIMI) through contract ANR-11-LABEX-0040-CIMI within they receive. Note that AFRA have been extended in
the program ANR-11-IDEX-0002-02. order to handle recursive support interactions together
p
P2 It is a conservative generalisation of Dung’s frame-
work for the definitions of conflict-free, admissible,
a n δ γ complete, preferred, and stable extensions.
For instance, in the proposed semantics, the conflict-
g β c free extensions of the framework of Fig. 3 are precisely
Dung’s conflict-free extensions: ∅, {a} and {b}. Besides,
α as we will see later, the attack α is valid with respect
to all three extensions because it is not the target of
Figure 2: Bob’s dilemma: arguments are in circle and any attack. It is worth noting that, despite its concep-
attacks in square. tual difference with respect to AFRA, we are able to
prove an one-to-one correspondence between our com-
plete, preferred and stable extensions and the corre-
with recursive attacks [9; 10]. However, when supports sponding AFRA extensions, in which the set of “accept-
are removed, these approaches go back to AFRA. able” arguments are the same. This offers an alternative
A similar work is described in [7] using the addition view for the semantics of recursive attacks that we be-
of meta-arguments that enable to encode the notions of lieve to be closer to Dung’s intuitive understanding.
“grounded attack” and “valid attack”. The notion of
grounded attack is about the source of the attack and 2 Background
the notion of valid attack is about the link between the
source and the target of the attack (i.e. the role of Definition 1. A Dung’s abstract argumentation frame-
the interaction itself). Despite the intuitive results ob- work (D-framework for short) is a pair AF = hA,Ri
tained by these approaches regarding complete, stable or where A is a set of arguments and R ⊆ A × A is a
grounded extensions, it somehow changes the role that relation representing attacks over arguments.
attacks play in Dung’s frameworks. For instance, the graph depicted in Fig. 3 corresponds
Example 3. Consider the argumentation framework to the D-framework AF3 = hA3 , R3 i with the set of argu-
corresponding to Fig. 3. According to Dung’s theory, this ments A3 = {a, b} and the attack relation R3 = {(a, b)}.
Definition 2. Given some D-framework AF = hA,Ri
and some set of arguments S ⊆ A, an argument a ∈ A
a α b
is said to be
i) defeated w.r.t. S iff ∃b ∈ S such that (b, a) ∈ R, and
Figure 3: A simple Dung’s framework
ii) acceptable w.r.t. S iff for every argument b ∈ A with
(b, a) ∈ R, there is c ∈ S such that (c, b) ∈ R.
framework has three conflict-free sets: ∅, {a} and {b}.
On the other hand, {a, b} is a conflict-free set accord- To obtain shorter definitions we will also use the follow-
ing to AFRA because the attack α is not in the set. In ing notations:
fact, in AFRA, such an argumentation framework can Def (S) def
= {a∈A ∃b ∈ S s.t. (b, a) ∈ R }
be turned into an AF by converting α into a new argu- def
Acc(S) = { a ∈ A ∀b ∈ A, (b, a) ∈ R implies b ∈ Def (S) }
ment as in Fig. 4. In this new framework, it is easy to
respectively denote the set of all defeated and acceptable
a α b arguments w.r.t. S.
Definition 3. Given a D-framework AF = hA, Ri, a
Figure 4: AF framework for AFRA of Fig. 3 set of arguments S ⊆ A is said to be
i) conflict-free iff S ∩ Def (S) = ∅,
observe that {a, b} is considered conflict-free in AFRA ii) admissible iff it is conflict-free and S ⊆ Acc(S),
because there is no attack between a and b. In some
iii) complete iff it is conflict-free and S = Acc(S),
sense, the connection between an attack and its source
has been lost. As another example of this behaviour, the iv) preferred iff it is ⊆-maximal1 admissible,
set {α, b} is not AFRA-conflict-free despite the fact that v) stable iff it is conflict-free and S ∪ Def (S) = A.
the source of α, the argument a, is not in the set. Theorem 1 ([11]). Given a D-framework AF = hA, Ri,
In this paper, we study an alternative semantics for the following assertions hold:
argumentation frameworks with recursive attacks based i) every complete set is also admissible,
on the following intuitive principles: ii) every preferred set is also complete, and
P1 The role played in Dung’s argumentation frame- iii) every stable set is also preferred.
works by attacks in defeating arguments is now For instance, in Example 3, the argument a is accepted
played by a subset of these attacks, which is exten- w.r.t. any set S because there is no argument x ∈ A such
sion dependent and represents the “valid attacks”
1
with respect to that extension. With ⊆ denoting the standard set inclusion relation.
that (x, a) ∈ R. Furthermore, b is defeated and non- of defeated arguments (Definition 2) using the set Γ in-
acceptable w.r.t. the set {a}. Then, it is easy to check stead of the attack relation R: given a structure of the
that {a} is stable (and, thus, conflict-free, admissible, form A = hS, Γi, we define:
complete and preferred). The empty set ∅ is admissible,
but not complete; and the set {b} is conflict-free, but not Def (A) def
= { a ∈ A ∃α ∈ Γ, s(α) ∈ S and t(α) = a } (1)
admissible.
In other words, an argument a ∈ A is defeated w.r.t. A
iff there is a “valid attack” w.r.t. A that targets a and
3 Semantics for recursive attacks whose source is “acceptable” w.r.t. A. It is interesting to
Definition 4. A recursive argumentation framework observe that we may define the attack relation associated
RAF = hA,K,s,ti is a quadruple where A and K are with some structure A = hS, Γi as follows:
(possibly infinite) disjunct sets respectively representing
arguments and attack names, and where s : K −→ A RA def
= { (s(α), t(α)) α ∈ Γ } (2)
and t : K −→ A ∪ K are functions respectively mapping
each attack to its source and its target. and that, using this relation, we can rewrite (1) as:
For instance, the argumentation framework of Ex- Def (A) def
= { a ∈ A ∃b ∈ S s.t. (b, a) ∈ RA } (3)
ample 3 corresponds to RAF3 = hA3 , K3 , s3 , t3 i where
A3 = {a, b}, K3 = {α}, s3 (α) = a and t3 (α) = b. Now, it is easy to see that our definition can be obtained
In general, given any D-framework AF = hA,Ri, we from Dung’s definition of defeat (Definition 2) just by
may obtain its corresponding argumentation framework replacing the attack relation R by the attack relation
RAF = hA,K,s,ti by defining a set of attack names RA associated with the structure A, or in other words,
K = { α(a,b) (a, b) ∈ R }. Functions s and t are straight- by replacing the set of all attacks in the argumentation
forwardly defined by mapping each attack (a, b) ∈ R as framework by the set of the “valid attacks” w.r.t. the
follows: s(α(a,b) ) = a and t(α(a,b) ) = b. structure A, as stated in P1. Analogously, by
It is worth noting that our definition allows the ex-
istence of several attacks between the same arguments. Inh(A) def
= {α∈K ∃b ∈ S s.t. (b, α) ∈ RA } (4)
Though this does not make any difference for frameworks
without recursive attacks, for recursive ones, it allows we denote a set of attacks that, intuitively, represents
representing attacks between the same arguments that the “inhibited attacks3 ” w.r.t. A.
are valid in different contexts. For instance, in the exam- We are now ready to extend the definition of accept-
ple of Figure 5, there are two attacks between a and b, able argument w.r.t. a set (Definition 2):
Definition 6 (Acceptability). An element x ∈ (A ∪ K)
c γ α is said to be acceptable w.r.t. some structure A iff every
attack α ∈ K with t(α) = x satisfies one of the following
a b conditions: (i) s(α) ∈ Def (A) or (ii) α ∈ Inh(A).
By Acc(A), we denote the set containing all acceptable
d δ β arguments and attacks with respect to A. We also define
the following order relations that will help us defining
Figure 5: A recursive framework representing attacks in preferred structures: for any pair of structures A = hS, Γi
different contexts and A0 = hS 0 , Γ0 i, we write A v A0 iff (S ∪ Γ) ⊆ (S 0 ∪ Γ0 )
and we write A var A0 iff S ⊆ S 0 . As usual, we say that a
structure A is v-maximal (resp. var -maximal) iff every
namely α and β, which represent different contexts as A0 that satisfies A v A0 (resp. A var A0 ) also satisfies
they are attacked by different arguments. A0 v A (resp. A0 var A).
Definition 5 (Structure). A pair A = hS, Γi is said to
be a structure of some RAF = hA,K,s,ti iff it satisfies: Definition 7. A structure A = hS, Γi is said to be:
S ⊆ A and Γ ⊆ K. i) conflict-free iff S ∩Def (A) = ∅ and Γ∩Inh(A) = ∅,
ii) admissible iff it is conflict-free and
Intuitively, the set S represents the set of “acceptable”
(S ∪ Γ) ⊆ Acc(A),
arguments w.r.t. the structure A, while Γ represents the
set of “valid attacks” w.r.t. A. Any attack2 α ∈ Γ is un- iii) complete iff it is conflict-free and Acc(A) = (S ∪ Γ),
derstood as non-valid and, in this sense, it cannot defeat iv) preferred iff it is a v-maximal admissible structure,
the argument or attack that it is targeting. v) arg-preferred iff it is a var-maximal preferred
For the rest of this section we assume that all def- structure,
initions and results are relative to some given frame- vi) stable4 iff S = Def (A) and Γ = Inh(A).
work RAF = hA,K,s,ti. We extend now the definition
Example 1 (cont’d) Let RAF be the recursive argu-
2
By Γ def
= K\Γ we denote the set complement of Γ. mentation framework corresponding to Fig. 6 (Fig. 6 is
a α b
of acceptable elements. Then, (i) A0 = A ∪ {x} is an
admissible structure, and (ii) y ∈ Acc(A0 ).
β Moreover, admissible structures form a complete partial
order with preferred structures as maximal elements:
c Proposition 1. The set of all admissible structures
forms a complete partial order with respect to v. Fur-
Figure 6: An acyclic recursive framework thermore, for every admissible structure A, there exists
an (arg-)preferred one A0 such that A v A0 .
The following result shows that the usual relation be-
Fig. 1 completed with the attack names). It is easy to tween extensions also holds for structures.
check that this framework has a unique complete, pre-
Theorem 2. The following assertions hold:
ferred and stable structure A = h{a, b, c}, {β}i. Further-
more, there are nine admissible structures that are not i) every complete structure is also admissible,
complete: h{a, c}, {β}i, h{b, c}, {β}i, h{a}, {β}i, h{c}, {β}i, ii) every preferred structure is also complete, and
h∅, {β}i, h{a, c}, ∅i, h{a}, ∅i, h{c}, ∅i and h∅, ∅i. There are iii) every stable structure is also preferred.
also other conflict-free structures that are not admis- Example 5. As a further example, consider the frame-
sible: h∅, {α, β}i, h{a}, {α, β}i, h{b}, {α, β}i, h{a, b}, {β}i, work RAF corresponding to Fig. 8. This framework
h{b}, {β}i, h{a, c}, {α}i, h{b, c}, {α}i, h{a}, {α}i, h{b}, {α}i,
h{c}, {α}i, h∅, {α}i, h{a, b}, ∅i, h{a, b, c}, ∅i, h{b, c}, ∅i and a α b
h{b}, ∅i.
It is worth to mention that preferred and arg-preferred β γ
structures do not necessarily coincide, since there exist
preferred structures that do not contain a maximal set c
of arguments as shown by the following example:
Example 4. Let RAF be the argumentation framework Figure 8: A cyclic recursive framework
corresponding to the the graph depicted in Figure 7. Both
has a unique complete and (arg-)preferred structure A =
a α b h{a, c}, {γ}i, but no stable one. Note that α and β are
neither acceptable nor inhibited w.r.t. A: β is not inhib-
β ited because b is not in the structure, so α is not accept-
able. α is not inhibited because β is not in the structure.
Figure 7: A RAF in which preferred and arg-preferred And β is not acceptable because b is not defeated (as α
structures do not coincide is not in the structure).
A = h{a, b}, {β}i and A0 = h{a}, {α, β}i are preferred Example 2 (cont’d) Consider the framework RAF
structures of RAF, but only the former contains a max- represented in Fig. 2. This framework has a unique
imal set of arguments and thus A is the unique arg- complete, preferred and stable structure: A0 =
preferred structure. h{a, g, p}, {α, , γ, δ}i. Among the 63 admissible struc-
tures, we find A1 = h{a}, {}i, A2 = h{a}, {, δ}i, and
We show now5 that, as in Dung’s argumentation the- A3 = h{a}, {α, , γ, δ}i.
ory, there is also a kind of Fundamental Lemma for
argumentation frameworks with recursive attacks. For
the sake of compactness, we will adopt the following 4 Relation with AFRA
notations: Given a structure A = hS, Γi and a set In this section, we establish correspondences between
T ⊆ (A ∪ K) containing arguments and attacks, by our semantics for recursive attacks and the semantics
A ∪ T def
= hS ∪ (T ∩ A), Γ ∪ (T ∩ K)i we denote the result for AFRA. In [4] a recursive framework is turned into a
of extending A with the elements in T . Dung’s framework by adding new arguments and attacks
using the following notion of defeat:
Lemma 1 (Fundamental Lemma). Let A = hS, Γi be
an admissible structure and x, y ∈ Acc(A) be any pair Definition 8 (Defeat). Let RAF = hA,K,s,ti. An attack
α ∈ K is said to directly defeat x ∈ A ∪ K iff t(α) = x.
3
We will deepen about the intuition of inhibited attacks It is said to indirectly defeat β ∈ K iff α directly defeats
in Section 6. s(β). Then, α is said to defeat x ∈ A ∪ K iff α directly
4
By Def (A) def
= A\Def (A) we denote the non-defeated defeats x or α indirectly defeats x.
arguments. Similarly, by Inh(A) def = K\Inh(A) we denote For instance, in Example 5, it is easy to see that α di-
the non-inhibited attacks. Note also that S = Def (A) and rectly defeats b and indirectly defeats γ. Hence, α defeats
Γ = Inh(A) already implies conflict-freeness. both b and γ. Attacks β and γ directly defeat α and β,
5
The proofs of propositions, lemmas, theorems given in respectively. It has been shown in [4] that AFRA exten-
this paper can be found in [8]. sions can be characterized as the extensions of a Dung’s
framework whose new set of arguments contains both ii) if A is admissible, then EA is AFRA-admissible,
arguments and attacks and whose new attack relation is iii) if A is complete, then EA is AFRA-complete,
the defeat relation of Definition 8. In this sense, under iv) if A is preferred, then EA is AFRA-preferred,
v) if A is stable, then EA is AFRA-stable.
a α b
For the converse of Prop. 2, we need to introduce some
extra notation: Given some set E ⊆ (A ∪ K), by
β γ
SE def
= (E ∩ A), we denote the set of arguments of E.
Then, considering the structure A0 = hSE , (E ∩ K)i, by
c
= (E ∩K) ∪ { α ∈ (Acc(A0 )∩K) s(α) < E }
ΓE def (5)
we denote the set of “valid attacks” with respect to E.
Figure 9: AF framework for AFRA framework of Ex. 5 Finally, by AE def
= hSE , ΓE i, we denote the structure corre-
sponding to some AFRA-extension E. Here, we have to
AFRA, the argumentation framework of Example 5 is add attacks that do not belong to the AFRA-extension.
turned into the one in Fig. 9 and it can be checked that Intuitively, this is due to the fact that, in AFRA, an at-
it has a unique complete and preferred extension {a, c} tack is not acceptable whenever its source is not accept-
and no stable one. We recall next the formal definitions able [4, Lemma 1]. Hence, we need to add to the struc-
of AFRA from [4]: ture all those attacks that are non-AFRA-acceptable
Definition 9. Let RAF = hA,K,s,ti and E ⊆ (A ∪ K). only because of attacks towards their source.
Then, an element x ∈ (A ∪ K) is said to be AFRA- Proposition 3. Given a RAF = hA,K,s,ti and a set
acceptable w.r.t. E iff for every α ∈ K that defeats x, E ⊆ (A ∪ K), the following assertions hold:
there is β ∈ E that defeats α. i) if E is AFRA-conflict-free, then AE is conflict-free,
Definition 10 (AFRA-extensions). Let RAF = ii) if E is AFRA-admissible, then AE is conflict-free,
hA,K,s,ti and a set E ⊆ (A ∪ K), E is said to be: iii) if E is AFRA-complete, AE is a complete structure,
i) AFRA-conflict-free iff @α, x ∈ E s.t. α defeats x, iv) if E is AFRA-preferred, AE is a preferred structure,
ii) AFRA-admissible iff E is AFRA-conflict-free and v) if E is AFRA-stable, AE is a stable structure.
each element of E is AFRA-acceptable w.r.t. E, It is worth to emphasise that for an AFRA-admissible ex-
iii) AFRA-complete iff it is AFRA-admissible and ev- tension, Proposition 3 only ensures that the correspond-
ery x ∈ (A ∪ K) which is AFRA-acceptable w.r.t. E ing structure AE is a conflict-free structure. In fact, there
belongs to E, exist AFRA-admissible extensions, whose corresponding
iv) AFRA-preferred iff it is a ⊆-maximal structures are not admissible. For instance, consider-
AFRA-admissible extension,
v) AFRA-stable iff it is AFRA-conflict-free and, for a α b β c
every x ∈ (A ∪ K), x < E implies that x is defeated
by some α ∈ E. Figure 10: A Dung’s framework with two attacks
As illustrated by Example 3, AFRA does not preserve
Dung’s notion of conflict-freeness. ing the argumentation framework of Fig. 10, the set
{α, c} is AFRA-admissible, but the corresponding struc-
Observation 1. AFRA is not a conservative generali- ture h{c}, {α, β}i is not an admissible structure (since a
sation of Dung’s approach. is not in the structure). This discrepancy follows from
In order to characterize the relation between our ap- the fact that, in AFRA, α defeats β despite of the ab-
proach and AFRA, we will need the following notation. sence of a while in our approach attacks whose source is
Given some structure A = hS, Γi, by not accepted cannot defeat other arguments or attacks.
def This difference disappears if we consider what we call
EA = S ∪ { α ∈ Γ s(α) ∈ S }
closed sets. We say that E ⊆ (A ∪ K) is closed iff every
we denote its corresponding AFRA-extension. attack α ∈ (E ∩ K) satisfies s(α) ∈ E.
Note that the AFRA-extension corresponding to a Proposition 4. Let E be a closed AFRA-admissible ex-
given structure only contains the attacks of the struc- tension. Then, AE is an admissible structure.
ture whose source belongs to the structure. The other
Note that for conflict-freeness and admissibility, the
attacks of the structure do not appear in the AFRA-
correspondence is not necessarily one-to-one. For in-
extension. Intuitively, this selection is motivated by the
stance, A = h{a, c}, {α}i and A0 = h{a, c}, {α, β}i are
fact that any attack in an AFRA-extension directly car-
both admissible structures of the framework of Fig. 10
ries a conflict against its target, even if its source is not
and both of them correspond to the same AFRA-
accepted, something which we avoid in our framework.
admissible extension EA = EA0 = {a, c, α}. Recall that β
Proposition 2. Let RAF = hA,K,s,ti and a struc- is acceptable w.r.t. A0 because it is not attacked. How-
ture A = hS, Γi, the following assertions hold: ever, it is not AFRA-acceptable w.r.t. {a, c, α, β} be-
i) if A is conflict-free, then EA is AFRA-conflict-free, cause, in AFRA, α defeats β and α is not itself defeated
(in fact, {a, c, α, β} is not even AFRA-conflict-free). On It is worth to note that, in Dung’s argumentation
the other hand, note that only A0 is a complete struc- frameworks, every attack is considered as “valid” in the
ture. In fact, for complete structures the correspondence sense that it may affect its target. The following defini-
is one-to-one. tion strengthens the notion of structure by adding a kind
Let us denote by Afra(·) the function mapping each of reinstatement principle on attacks, that forces every
structure A to its corresponding AFRA-extension EA . attack that cannot be defeated to be “valid”.
Proposition 5. The following assertions hold: Definition 11 (D-structure). A d-structure A = hS, Γi
i) if E is AFRA-complete (or just a closed AFRA- is a structure that satisfies (Acc(A) ∩ K) ⊆ Γ.
conflict-free extension), then Afra(AE ) = E, and Definition 12. A conflict-free (resp. admissible, com-
ii) if A is a complete structure, then AAfra(A) = A. plete, preferred, stable) d-structure is a conflict-free
Theorem 3. The function Afra(·) is a one-to-one cor- (resp. admissible, complete, preferred, stable) structure
respondence between the sets of all complete (resp. pre- which is also a d-structure.
ferred and stable) structures and the set of all AFRA- As a direct consequence of Definition 7, we have:
complete (resp. preferred and stable) extensions. Observation 2. Every complete structure is also a
Note that given the one-to-one correspondence be- d-structure.
tween preferred structures and AFRA-preferred exten-
Observation 2 plus Theorem 3 immediately imply the
sions, there are AFRA-preferred extensions that do not
existence of a one-to-one correspondence between com-
correspond to arg-preferred ones and thus, they do not
plete (resp. preferred or stable) d-structures and their
contain a maximal set of arguments. For instance,
corresponding AFRA and Dung’s extensions. In order
{a, b, β} and {a, α} are both AFRA-preferred extensions
to establish a correspondence between conflict-free (resp.
in Example 4, but only the former contains a maximal
admissible) d-structures and their corresponding Dung’s
set of arguments.
extensions, we need to define what it means for a set of
An interesting consequence of Theorem 3 and Propo-
arguments to be an extension of some recursive frame-
sition 12 in [4] is that complexity for RAFs’ semantics
work.
does not increase w.r.t. Dung’s frameworks. That is,
credulous acceptance w.r.t. the complete, preferred and Definition 13 (Argument extensions). A set of argu-
the stable semantics is NP-complete. Sceptical accep- ments S ⊆ A is conflict-free (resp. admissible, com-
tance w.r.t. the preferred (resp. stable) semantics is plete, preferred, stable) iff there is some Γ ⊆ K such
ΠP2 -complete (resp. coNP-complete) [12].
that A = hS, Γi is a conflict-free (resp. admissible, com-
Example 2 (cont’d) For the framework repre- plete, preferred, stable) d-structure.
sented in Fig. 2, there is a unique AFRA-complete, Definition 13 allows us to talk about sets of argu-
AFRA-preferred and AFRA-stable extension: E = ments instead of structures. Before formalising the fact
{a, g, p, α, , γ}. Note that δ < E whereas E = EA0 . In- that Definition 13 characterizes a conservative general-
deed, no AFRA-admissible extension contains δ. Anal- isation of Dung’s argumentation framework, we define
ogously, we have EA1 = EA2 = EA3 = {a, }. More- the attack relation associated with some framework in a
over, among the AFRA-admissible extensions, we find similar way to the attack relation associated with some
{a, g, , γ} which is not closed. The associated structure structure: RRAF def= { (s(α), t(α)) α ∈ K }. Note that,
A4 = h{a, g}, {, γ}i is not an admissible structure. since every structure A = hS, Γi satisfies Γ ⊆ K, it
clearly follows that RA ⊆ RRAF . We also precise what
5 Conservative generalisation we mean by non-recursive framework:
As mentioned in the introduction, our theory aims to Definition 14 (Non-recursive framework). A frame-
be a conservative generalisation of Dung’s theory (P2). work RAF = hA,K,s,ti is said to be non-recursive iff
Indeed, given the one-to-one correspondence between RRAF ⊆ A×A.
complete, preferred and stable structures and their cor- That is, non-recursive frameworks are those in which
responding AFRA-extensions and between the latter no attack targets another attack. Given a non-recursive
and Dung’s extensions [4] in the case of non-recursive framework RAF, it is easy to observe that AF =
frameworks, it immediately follows that there exists a hA, RRAF i is a D-framework (Definition 1). In this sense,
one-to-one correspondence between complete, preferred by RAFD def = hA, RRAF i, we denote the D-framework as-
and stable structures and their corresponding Dung’s ex- sociated with some RAF.
tensions.
Observation 3. Every d-structure A = hS, Γi of any
On the other hand, this is not the case when
non-recursive framework satisfies Γ = K.
we consider only conflict-freeness or admissibility.
As mentioned in the introduction, {a, b} is an Theorem 4. A set of arguments S ⊆ A is conflict-free
AFRA-conflict-free extension of the non-recursive argu- (resp. admissible, complete, preferred or stable) w.r.t.
mentation framework of Example 3. From Proposition 3, some non-recursive RAF (Definition 13) iff it is conflict-
this implies that the corresponding structure h{a, b}, ∅i, free (resp. admissible, complete, preferred or stable)
is a conflict-free structure. w.r.t. RAFD (Definition 3).
Due to Observation 2, it follows directly that: obtained by removing the attack α from Γ. Further-
Corollary 1. A structure A = hS, Ki is complete (resp. more, by RAF−α = hA, K−α , s−α , t−α i, with s−α and
preferred, stable) w.r.t. a non-recursive RAF (Defini- t−α the restrictions of s and t to K−α , we denote
tion 7) iff S is complete (resp. preferred or stable) w.r.t. the framework obtained by removing the attack α from
RAF = hA,K,s,ti. Similarly, by A−α = hS, Γ−α i we de-
RAFD (Definition 3).
note the structure obtained by removing the attack α
It is worth to note that the notion of d-structure from the structure A = hS, Γi.
provides alternative semantics for the principles of
conflict-freeness and admissibility. Example 1 (cont’d) Let RAF be the recursive ar-
Example 1 (cont’d) Among the conflict-free struc- gumentation framework of Fig. 6. Then RAF−α =
tures that are not admissible, only five are conflict-free hA, ∅, s−α , t−α i with A = {a, b, c} because β ≺ α im-
d-structures: h∅, {α, β}i, h{a}, {α, β}i, h{b}, {α, β}i, plies that β < K−α . Furthermore, if A = h{a, b, c}, {β}i,
h{a, b}, {β}i, h{b}, {β}i. Similarly, among the admissi- then A−α = h{a, b, c}, ∅i which is a stable structure of
ble structures that are not complete, only five are admis- RAF−α .
sible d-structures: h{a, c}, {β}i, h{b, c}, {β}i, h{a}, {β}i, Proposition 6 below formalises the intuitions presented
h{c}, {β}i and h∅, {β}i. in the previous example.
Example 2 (cont’d) There are admissible structures Proposition 6. Let RAF be some framework, A be some
w.r.t. the framework represented in Fig. 2 that are not conflict-free (resp. admissible, complete, preferred, sta-
d-structures: for instance A1 and A2 . Indeed, each d- ble) structure and α ∈ Inh(A) be some inhibited attack
structure must contain the attacks thas are not targeted w.r.t. A. Then, A−α is a conflict-free (resp. admissible,
by any other attack, that is, {, α, δ}. Moreover each
complete, preferred, stable) structure of RAF−α .
d-structure containing a must also contain γ.
6 Inhibited attacks 7 Conclusion and future works
In this section, the intuition behind the concept of inhib- In this work we have extended Dung’s abstract argu-
ited attacks is deepened and precisely defined. Indeed, mentation framework with recursive attacks. One of the
we may expect that attacks that are inhibited do not essential characteristics of this extension is its conser-
have any effect on their targets, that is, we may remove vative nature with respect to Dung’s approach (when
them without modifying the condition of the structure. d-structures are considered). The other one is that se-
Example 6. Let RAF be the recursive argumentation mantics are given with respect to the notion of “valid at-
framework of Fig. 6 and A = h{a, b, c}, {β}i its unique tacks” which play a role analogous to attacks in Dung’s
complete structure. It is easy to check that α is inhibited frameworks. The notions of “grounded attack” and
w.r.t. A because c and β belong to the structure and α is “valid attack” have been introduced in [7]. However,
the target of β. According to the above intuition, we may these notions have been encoded through a two-step
expect that this would imply that there is a “somehow” translation into a meta-argumentation framework. In
corresponding structure A0 which is complete w.r.t. some the first step, a meta-argument is associated to an at-
RAF0 obtained by removing α. Note that, in this case, tack, and a support relation is added from the source of
removing α also implies removing β because there can- the attack to the meta-argument. In the second step,
not be attacks without target. In fact, the resulting RAF0 a support relation is encoded by the addition of a new
is a recursive framework with arguments {a, b, c} and no meta-argument and new attacks. So [7] uses a method
attack. It is easy to check that A0 = h{a, b, c}, ∅i is com- for flattening a recursive framework. As a consequence,
plete (also preferred and stable) w.r.t RAF0 and that it extensions contain different kinds of argument. In con-
shares with A the set of “acceptable” arguments. trast, we propose a theory where valid attacks remain
explicit, and distinct from arguments, within the notion
Let us now formalise this intuition: of structure. Despite these differences with respect to
Definition 15. Given some framework RAF and two other generalisations, we proved a one-to-one correspon-
different attacks β, α, we define: β ≺ α iff there is some dence with AFRA-extensions in the case of the complete,
chain of attacks δ1 , δ2 , . . . δn such that δ1 = β, δn = α preferred and stable semantics, while retaining a one-to-
and t(δi ) = δi+1 for 1 ≤ i < n. one correspondence with Dung’s frameworks in the case
of conflict-free and admissible extensions.
For instance, in the argumentation framework of For a better understanding of the RAF framework,
Fig. 6, we have that β ≺ α. On the other hand, neither future work should include the study of other seman-
α ≺ β, nor β ≺ α hold for the argumentation framework tics (stage, semi-stable, grounded and ideal), extend-
of Fig. 10. Note that ≺ is the empty relation for any ing our approach by taking into account bipolar inter-
non-recursive framework. As usual, by we denote the actions [9; 16] (case when arguments and attacks may
reflexive closure of ≺. be attacked or supported), and enriching the translation
Given an attack α, and a set of attacks Γ, by Γ−α def
= proposed by [5; 6; 13; 15] from Dung’s framework into
Γ\{ β ∈ K β α } we denote the set of attacks propositional logic and ASP, in order to capture RAF.
References [14] S. Modgil. Reasoning about preferences in argumen-
[1] L. Amgoud and C. Cayrol. A reasoning model based tation frameworks. Artif. Intell., 173(9-10):901–934,
on the production of acceptable arguments. Annals 2009.
of Mathematics and Artificial Intelligence, 34:197– [15] M. Osorio, J. C. Nieves, and A. Santoyo. Complete
216, 2002. extensions as clark’s completion semantics. In Proc.
[2] L. Amgoud, N. Maudet, and S. Parsons. Modelling of the Mexican International Conference on Com-
dialogues using argumentation. In Proc. of ICMAS, puter Science, pages 81–88, 2013.
pages 31–38, 2000. [16] S. Villata, G. Boella, D. M. Gabbay, and L. van der
[3] R. Arisaka and K. Satoh. Voluntary manslaugh- Torre. Modelling defeasible and prioritized support
ter? a case study with meta-argumentation with in bipolar argumentation. Annals of Maths and AI,
supports. In S. Kurahashi, Y. Ohta, S. Arai, 66(1-4):163–197, 2012.
K. Satoh, and D. Bekki, editors, New Frontiers
in Artificial Intelligence. JSAI-isAI 2016. Lecture
Notes in Computer Science, vol 10247, pages 241–
252. Springer, Cham, 2017.
[4] P. Baroni, F. Cerutti, M. Giacomin, and G. Guida.
AFRA: argumentation framework with recursive at-
tacks. Int. J. Approx. Reasoning, 52(1):19–37, 2011.
[5] P. Besnard and S. Doutre. Checking the acceptabil-
ity of a set of arguments. In J. P. Delgrande and
T. Schaub, editors, 10th International Workshop on
Non-Monotonic Reasoning (NMR 2004), Whistler,
Canada, June 6-8, 2004, Proceedings, pages 59–64,
2004.
[6] J. L. Carballido, J. C. Nieves, and M. Osorio. Infer-
ring preferred extensions by pstable semantics. In-
teligencia artificial: Revista Iberoamericana de In-
teligencia Artificial, 13(41):38–53, 2009.
[7] C. Cayrol, A. Cohen, and M-C. Lagasquie-Schiex.
Towards a new framework for recursive interac-
tions in abstract bipolar argumentation. In Proc.
of COMMA, pages 191–198, 2016.
[8] C. Cayrol, J. Fandinno, L. Fariñas del Cerro, and
M-C. Lagasquie-Schiex. Valid attacks in argumen-
tation frameworks with recursive attacks. Technical
Report RR–2017-16–FR, IRIT, 2017.
[9] A. Cohen, S. Gottifredi, A. J. Garcı́a, and G. R.
Simari. An approach to abstract argumentation
with recursive attack and support. J. Applied Logic,
13(4):509–533, 2015.
[10] A. Cohen, S. Gottifredi, A. J. Garcı́a, and G. R.
Simari. On the acceptability semantics of argumen-
tation frameworks with recursive attack and sup-
port. In Proc. of COMMA, pages 231–242, 2016.
[11] P. M. Dung. On the acceptability of arguments
and its fundamental role in nonmonotonic reason-
ing, logic programming and n-person games. Artif.
Intell., 77(2):321–358, 1995.
[12] P. E. Dunne. Computational properties of argument
systems satisfying graph-theoretic constraints. Ar-
tif. Intell., 171(10-15):701–729, 2007.
[13] U. Egly, S. A. Gaggl, and S. Woltran. Answer-set
programming encodings for argumentation frame-
works. Argument & Computation, 1(2):147–177,
2010.