### 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 which attacks the argument C:

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

There are two possibilities:

• First, one can consider that the cycle is like an infinite branch; so (resp. ) is the root of one branch whose length is . But the parity of the length of this branch is undefined, and it is impossible to say if this branch is an attack branch or a defence branch.

• The second possibility is to consider that the cycle is like an infinity of branches; so (resp. ) is the root of an infinity of attack branches and defence branches whose lengths are known and finite.

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

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

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

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:

The and 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 an unattacked cycle. The graph which contains is rewritten as follows:
1. the cycle is removed,
2. and replaced by the infinite acyclic graphs, one for each , :
 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
3. the edges between each of the and an argument which does not belong to are kept.

Example 7 - Unattacked cycle (continuation) The graph containing the unattacked cycle and the argument , which is attacked by , is rewritten as follows:

 ... ... ... ... ... ...
 ... ... ... ... ... ...

where the and are new arguments.

Definition 12 (Rewriting of an attacked cycle)   Let an attacked cycle, the direct attacker of each is denoted , if it exists. The graph which contains is rewritten as follows:
1. the cycle is removed,
2. and replaced by the infinite acyclic graphs, one for each :
 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
(the branches leading to exist iff exists20).
3. the edges between each of the and an argument which does not belong to are kept.
4. the edges between each of the and an argument which does not belong to are kept.

Example 8 - Attacked cycle (continuation) The graph containing the cycle attacked in by the argument and with the argument (resp. ) attacked by (resp. ) is rewritten as follows:

 ... ... ... ... ... ... ... ... ... ...
 ... ... ... ... ... ... ... ... ... ... ... ...

where the and are new arguments.

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

• If they are not interconnected, we rewrite each cycle, and the valuation of the resulting graph after rewriting does not depend on the order of cycles we select to rewrite because the valuation process only uses the length of the branches.
• If they are interconnected, they are considered as a metacyle which is in turn attacked or unattacked and the previous methodology can be used leading to a more complex rewriting process which is not formalized here (see details and examples in Appendix B).

Marie-Christine Lagasquie 2005-02-04