The framework of [9] and its graphical representation

We consider the abstract framework introduced in [9]. An argumentation system ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$ is a set ${\mathcal{A}}$ of arguments and a binary relation ${\mathcal{R}}$ on ${\mathcal{A}}$ called an attack relation: consider $A_i$ and $A_j\in {\mathcal{A}}$, $A_i {\mathcal{R}}
A_j$ means that $A_i$ attacks $A_j$ or $A_j$ is attacked by $A_i$ (also denoted by $(A_i, A_j) \in {\mathcal{R}}$).

An argumentation system is well-founded if and only if there is no infinite sequence $A_0$, $A_1$, ..., $A_n$, ...such that $\forall i, A_i \in {\mathcal{A}}$ and $A_{i+1} {\mathcal{R}}A_i$.

Here, we are not interested in the structure of the arguments and we consider an arbitrary attack relation.

Notation: ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$ defines a directed graph ${\mathcal{G}}$ called the attack graph. Consider $A \in {\mathcal{A}}$, the set ${\mathcal{R}}^-(A)$ is the set of the arguments attacking $A$6and the set ${\mathcal{R}}^+(A)$ is the set of the arguments attacked by $A$7.

Example 1  
The system ${<}{\mathcal{A}}= \{ A_1, A_2, A_3, A_4\}, {\mathcal{R}}= \{(A_2, A_3),
(A_4, A_3), (A_1, A_2)\}{>}$ defines the following graph ${\mathcal{G}}$ with the root8 $A_3$:

% latex2html id marker 8867

Definition 1 (Graphical representation of an argumentation system)   Let ${\mathcal{G}}$ be the attack graph associated with the argumentation system ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$, we define:

Leaf of the attack graph
A leaf of ${\mathcal{G}}$ is an argument $A \in {\mathcal{A}}$ without attackers9.

Path in the attack graph
A path from $A$ to $B$ is a sequence of arguments ${\mathcal{C}}= A_1-\ldots-A_n$ such that:
  • $A=A_1$,
  • $A_1 {\mathcal{R}}A_2$,
  • ...,
  • $A_{n-1} {\mathcal{R}}A_n$,
  • $A_n = B$.
The length of the path is $n-1$ (the number of edges that are used in the path) and will be denoted by $l_{{\mathcal{C}}}$.

A special case is the path10 from $A$ to $A$ whose length is $0$.

The set of paths from $A$ to $B$ will be denoted by ${\mathcal{C}}(A,

Dependence, independence, root-dependence of a path

Consider 2 paths ${\mathcal{C}}_A \in {\mathcal{C}}(A_1, A_n)$ and ${\mathcal{C}}_B \in
{\mathcal{C}}(B_1, B_m)$.

These two paths will be said dependent iff % latex2html id marker 2983
$\exists A_i \in
{\mathcal{C}}_A$, % latex2html id marker 2985
$\exists B_j \in {\mathcal{C}}_B$ such that $A_i = B_j$. Otherwise they are independent.

These two paths will be said root-dependent in $A_n$ iff $A_n = B_m$ and $\forall A_i \neq A_n \in {\mathcal{C}}_A$, % latex2html id marker 2995
\in {\mathcal{C}}_B$ such that $A_i = B_j$.

Cycles in the attack graph
A cycle11 is a path ${\mathcal{C}}= A_1-\ldots-A_n-A_1$ such that $\forall i, j \in [1,n]$, if $i\neq j$, then $A_i \neq A_j$.

A cycle ${\mathcal{C}}$ is isolated iff $\forall A \in {\mathcal{C}}$, % latex2html id marker 3011
$\not\exists B \in {\mathcal{A}}$ such that $B {\mathcal{R}}A$ and $B \not\in

Two cycles ${\mathcal{C}}_A = A_1-\ldots-A_n-A_1$ and ${\mathcal{C}}_B =
B_1-\ldots-B_m-B_1$ are interconnected iff % latex2html id marker 3021
$\exists i \in
[1,n], \exists j \in [1,m]$ such that $A_i = B_j$.

We use the notions of direct and indirect attackers and defenders. The notions introduced here are inspired by related definitions first introduced in [9] but are not strictly equivalent12.

Definition 2 (Direct/Indirect Attackers/Defenders of an argument)   Consider $A \in {\mathcal{A}}$:

If the argument $A$ is an attacker (direct or indirect) of the argument $B$, we say that $A$ attacks $B$ (or that $B$ is attacked by $A$). In the same way, if the argument $A$ is a defender (direct or indirect) of the argument $B$, then $A$ defends $B$ (or $B$ is defended by $A$).

Note that an attacker can also be a defender (for example, if $A_1$ attacks $A_2$ which attacks $A_3$, and $A_1$ also attacks $A_3$). In the same way, a direct attacker can be an indirect attacker (for example, if $A_1$ attacks $A_2$ which attacks $A_3$ which attacks $A_4$, and $A_1$ also attacks $A_4$) and the same thing may occur for the defenders.

Definition 3 (Attack branch and defence branch of an argument)   Consider $A \in {\mathcal{A}}$, an attack branch (resp. defence branch) for $A$ is a path in ${\mathcal{G}}$ from a leaf to $A$ whose length is odd (resp. even). We say that $A$ is the root of an attack branch (resp. a defence branch).

Note that this notion of defence is the basis of the usual notion of reinstatement ($B$ attacks $C$, $A$ attacks $B$ and $C$ is ``reinstated'' because of $A$). In this paper, reinstatement is taken into account indirectly, because the value of the argument $C$ and the possibility for selecting $C$ will be increased thanks to the presence of $A$.

All these notions are illustrated on the following example:

Example 2  
% latex2html id marker 8999
On this graph ${\mathcal{G}}$, we can see:
  • a path from $C_2$ to $A$ whose length is 2 ($C_2-B_1-A$),
  • 2 cycles $A_1-A_3-A_2-A_1$ and $A_1-A_3-A_4-A_1$, of length 3, which are not isolated (note that $A_1-A_3-A_2-A_1-A_3-A_4-A_1$ is not a cycle with our definition),
  • the two previous cycles are interconnected (in $A_1$ and $A_3$),
  • the paths $D_1-C_1-B_1$ and $C_3-B_2-A$ are independent, the paths $D_1-C_1-B_1-A$ and $C_3-B_2-A$ are root-dependent and the paths $D_1-C_1-B_1-A$ and $C_2-B_1-A$ are dependent,
  • $D_1$, $C_2$, $E_1$ are the leaves of ${\mathcal{G}}$,
  • $D_1-C_1-B_1-A$ is an attack branch for $A$ whose length is 3, $C_2-B_1-A$ is a defence branch for $A$ whose length is 2,
  • $C_2$, $B_1$ and $B_2$ are the direct attackers of $A$,
  • $C_1$, $C_2$ (which is already a direct attacker of $A$) and $C_3$ are the direct defenders of $A$,
  • $D_1$ and $D_2$ are the two indirect attackers of $A$,
  • $E_1$ is the only indirect defender of $A$.

Marie-Christine Lagasquie 2005-02-04