Study of cycles

Handling cycles raises some important issues: the notion of branch is not always useful in a cycle (for example, in an unattacked cycle like in Examples 5 and 7), and when this notion is useful, the length of a branch can be defined in different ways.

Let us consider different examples:

Example 7 (Unattacked cycle)   The graph is reduced to an unattacked cycle $A-B-A$ which attacks the argument C:

\includegraphics[scale=0.7]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/cas10bis.eps}

The notion of branch is useless in this case, because there is no leaf in the graph.

There are two possibilities:

The second possibility means that the cycle may have two representations which are acyclic but also infinite graphs (one with the root $A$ and the other one with the root $B$). This is a rewriting process of the cycle:

\includegraphics[scale=0.75]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/cas10-trad.eps}

The $A_i$ and $B_i$ must be new arguments created during the rewriting process of the cycle.

Example 8 (Attacked cycle)   The cycle $A-B-A$ is attacked by at least one argument which does not belong to the cycle (here, the attacker is the unattacked argument $D$):

% latex2html id marker 9478
\includegraphics[scale=0.7]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/ex-circuit2.eps}

In this case, the notion of branch is useful because there exists one leaf in the graph, but the difficulty is to compute the length of this branch. As in Example 7, we can consider either that there is only one infinite branch (so, it is impossible to know if this branch is an attack or a defence branch), or that there is an infinity of attack branches and defence branches whose lengths are known and finite.

In the second case, the graph can be rewritten into the following structures:

% latex2html id marker 9480
\includegraphics[scale=0.7]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/ex-circuit2-trad2.eps}

The $A_i$ and $B_i$ must be new arguments created during the rewriting process of the graph.

From the previous examples, we have chosen to manage a cycle as an infinity of attack branches and defence branches whose lengths are known and finite because we would like to be able to apply Definition 10 in all cases (acyclic graphs and graphs with cycles). However, we need a rewriting process of the graph with cycles into an acyclic graph. There are two different cases, one for the unattacked cycles and one for the attacked cycles:

Definition 11 (Rewriting of an unattacked cycle)   Let ${\mathcal{C}}= A_0-A_1-\ldots-A_{n-1}-A_0$ an unattacked cycle. The graph ${\mathcal{G}}$ which contains ${\mathcal{C}}$ is rewritten as follows:
  1. the cycle ${\mathcal{C}}$ is removed,
  2. and replaced by the infinite acyclic graphs, one for each $A_i$, $i= 0 \ldots n - 1$:
        $A_i$        
    $\nearrow$ $\nearrow$ ... $\nwarrow$ $\nwarrow$ $\nwarrow$ ...
    ${A_i}_1^1$ ${A_i}_1^2$ ... ${A_i}_1^{n-1}$ ${A_i}_1^n$ ${A_i}_1^{n+1}$ ...
      $\uparrow$ ... $\uparrow$ $\uparrow$ $\uparrow$ ...
      ${A_i}_2^2$ ... ${A_i}_2^{n-1}$ ${A_i}_2^n$ ${A_i}_2^{n+1}$ ...
        ... ... ... ... ...
          $\uparrow$ $\uparrow$ $\uparrow$ ...
          ${A_i}_{n-1}^{n-1}$ ${A_i}_{n-1}^n$ ${A_i}_{n-1}^{n+1}$ ...
            $\uparrow$ $\uparrow$ ...
            ${A_i}_n^n$ ${A_i}_n^{n+1}$ ...
              $\uparrow$ ...
              ${A_i}_{n+1}^{n+1}$ ...
  3. the edges between each of the $A_i$ and an argument which does not belong to ${\mathcal{C}}$ are kept.

Example 7 - Unattacked cycle (continuation) The graph ${\mathcal{G}}$ containing the unattacked cycle $A-B-A$ and the argument $C$, which is attacked by $A$, is rewritten as follows:

$C$
$\uparrow$
$A$
$\nearrow$ $\nearrow$ $\nwarrow$ ...
${A}_1^1$ ${A}_1^2$ ${A}_1^3$ ...
  $\uparrow$ $\uparrow$ ...
  ${A}_2^2$ ${A}_2^3$ ...
    $\uparrow$ ...
    ${A}_3^3$ ...
$B$
$\nearrow$ $\nearrow$ $\nwarrow$ ...
${B}_1^1$ ${B}_1^2$ ${B}_1^3$ ...
  $\uparrow$ $\uparrow$ ...
  ${B}_2^2$ ${B}_2^3$ ...
    $\uparrow$ ...
    ${B}_3^3$ ...

where the ${A}_k^l$ and ${B}_k^l$ are new arguments.

Definition 12 (Rewriting of an attacked cycle)   Let ${\mathcal{C}}= A_0-A_1-\ldots-A_{n-1}-A_0$ an attacked cycle, the direct attacker of each $A_i$ is denoted $B_i$, if it exists. The graph ${\mathcal{G}}$ which contains ${\mathcal{C}}$ is rewritten as follows:
  1. the cycle ${\mathcal{C}}$ is removed,
  2. and replaced by the infinite acyclic graphs, one for each $A_i$ $i= 0 \ldots n - 1$:
        $A_i$        
    $\nearrow$ $\nearrow$ ... $\nwarrow$ $\nwarrow$ $\nwarrow$ ...
    $B_i$ ${A_i}_1^1$ ... ${A_i}_1^{n-1}$ ${A_i}_1^n$ ${A_i}_1^{n+1}$ ...
      $\uparrow$ ... $\uparrow$ $\uparrow$ $\uparrow$ ...
      % latex2html id marker 3945
$B_{(i-1+n) \mbox{\scriptsize { mod }}n}$ ... ${A_i}_2^{n-1}$ ${A_i}_2^n$ ${A_i}_2^{n+1}$ ...
        ... ... ... ... ...
          $\uparrow$ $\uparrow$ $\uparrow$ ...
          ${A_i}_{n-1}^{n-1}$ ${A_i}_{n-1}^n$ ${A_i}_{n-1}^{n+1}$ ...
          $\uparrow$ $\uparrow$ $\uparrow$ ...
          % latex2html id marker 3971
$B_{(i+1) \mbox{\scriptsize { mod }}n}$ ${A_i}_n^n$ ${A_i}_n^{n+1}$ ...
            $\uparrow$ $\uparrow$ ...
            $B_i$ ${A_i}_{n+1}^{n+1}$ ...
              $\uparrow$ ...
              % latex2html id marker 3987
$B_{(i-1+n) \mbox{\scriptsize { mod }}n}$ ...
    (the branches leading to $B_k$ exist iff $B_k$ exists20).
  3. the edges between each of the $A_i$ and an argument which does not belong to ${\mathcal{C}}$ are kept.
  4. the edges between each of the $B_i$ and an argument which does not belong to ${\mathcal{C}}$ are kept.

Example 8 - Attacked cycle (continuation) The graph ${\mathcal{G}}$ containing the cycle $A-B-A$ attacked in $A$ by the argument $D$ and with the argument $C$ (resp. $E$) attacked by $A$ (resp. $B$) is rewritten as follows:

$C$
$\uparrow$
$A$
$\nearrow$ $\uparrow$ $\nwarrow$ ...
$D$ ${A}_1^2$ ${A}_1^4$ ...
  $\uparrow$ $\uparrow$ ...
  ${A}_2^2$ ${A}_2^4$ ...
  $\uparrow$ $\uparrow$ ...
  $D$ ${A}_3^4$ ...
    $\uparrow$ ...
    ${A}_4^4$ ...
    $\uparrow$ ...
    $D$ ...
$E$
$\uparrow$
$B$
$\nearrow$ $\uparrow$ $\nwarrow$ ...
${B}_1^1$ ${B}_1^3$ ${B}_1^5$ ...
$\uparrow$ $\uparrow$ $\uparrow$ ...
$D$ ${B}_2^3$ ${B}_2^5$ ...
  $\uparrow$ $\uparrow$ ...
  ${B}_3^3$ ${B}_3^5$ ...
  $\uparrow$ $\uparrow$ ...
  $D$ ${B}_4^5$ ...
    $\uparrow$ ...
    ${B}_5^5$ ...
    $\uparrow$ ...
    $D$ ...

where the ${A}_k^l$ and ${B}_k^l$ are new arguments.

Note: If there exist several cycles in a graph, we have two cases.

Marie-Christine Lagasquie 2005-02-04