Gradual valuation with tuples for acyclic graphs

First, in order to record the lengths of the branches leading to the arguments, we use the notion of tuples and we define some operations on these tuples:

Definition 7 (Tuple)   A tuple is a sequence of integers. The tuple $\underbrace{(0,
\ldots, 0, \ldots)}_{\infty}$ will be denoted by $0^{\infty}$. The tuple $\underbrace{(1, \ldots, 1, \ldots)}_{\infty}$ will be denoted by $1^{\infty}$.

Notation 1   ${\mathcal{T}}$ denotes the set of the tuples built with positive integers.

Definition 8 (Operations on the tuples)   We have two kinds of operations on tuples:

Note that we allow infinite tuples, among other reasons, because they are needed later in order to compute the ordering relations described in Section 3.2.4 (in particular when the graph is cyclic).

The operations on the tuples have the following properties:

Property 7 (Properties of $\star$ and $\oplus$)  
The concatenation $\star$ is commutative and associative.

For any tuple $t$ and any integers $k$ and $k'$, $(t \oplus k)
\oplus k' = t \oplus (k + k')$.

For any integer $k$ and any tuples $t$ and $t'$ different from $0^{\infty}$17, $(t \star t') \oplus k = (t \oplus k) \star (t' \oplus k)$.

In order to valuate the arguments, we split the set of the lengths of the branches leading to the argument in two subsets, one for the lengths of defence branches (even integers) and the other one for the lengths of attack branches (odd integers). This is captured by the notion of tupled values:

Definition 9 (Tupled value)   A tupled value is a pair of tuples $vt = [vt_p, vt_i]$ with:

Notation 2   ${\mathcal{V}}$ denotes the subset of ${\mathcal{T}}\times {\mathcal{T}}$ of all tupled values (so, $\forall vt \in {\mathcal{V}}$, $vt$ is a pair of tuples satisfying Definition 9).

Using this notion of tupled-values, we can define the computation process of the gradual valuation with tuples18 in the case of acyclic graphs.

Definition 10 (Valuation with tuples for acyclic graphs)   Let ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$ be an argumentation system without cycles. A valuation with tuples is a function $v: {\mathcal{A}}\to {\mathcal{V}}$ such that:

If $A \in {\mathcal{A}}$ is a leaf then

$v(A) = [0^{\infty},()]$.

If $A \in {\mathcal{A}}$ has direct attackers denoted by $B_1$, ..., $B_n$, ...then

$v(A) = [v_p(A), v_i(A)]$ with:
$v_p(A) = (v_i(B_1) \oplus 1) \star \ldots \star (v_i(B_n) \oplus 1)
\star \ldots $

$v_i(A) = (v_p(B_1) \oplus 1) \star \ldots \star (v_p(B_n) \oplus 1)
\star \ldots $

Notes: The choice of the value $[0^{\infty},()]$ for the leaves is justified by the fact that the value of an argument memorises all the lengths of the branches leading to the argument. Using the same constraint, either $v_p(A)$ or $v_i(A)$ may be empty but not both19.

Note also that the set of the direct attackers of an argument can be infinite (this property will be used when we take into account an argumentation graph with cycles).

Example 6   On this graph, the valuation with tuples gives the following results:

% latex2html id marker 9441
\includegraphics[scale=0.6]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/ex-notionster.eps}
On this graph ${\mathcal{G}}$, we have:
  • $v(D_1) = v(C_2) = v(E_1) = [0^{\infty},()]$,
  • $v(C_1) = v(D_2) = [(),(1)]$,
  • $v(C_3) = [(2),()]$,
  • $v(B_1) = [(2),(1)]$,
  • $v(B_2) = [(),(3)]$,
  • $v(A) = [(2,4),(1,3)]$.

Marie-Christine Lagasquie 2005-02-04