\documentclass[twoside,11pt]{article}
%\documentstyle[jair,twoside,11pt,theapa]{article}
   
\usepackage{alltt}
%\usepackage[nolineno]{lgrind}
%\usepackage{epic}
%\usepackage{eepic}
%\usepackage{ecltree} 
%\usepackage{myfullpage}
\usepackage{amssymb}
%\usepackage{longtable}
\usepackage{dsfont}
\usepackage[dvips]{graphicx}
\usepackage[ruled]{algorithm2e}
%\usepackage[french]{varioref}
    
\usepackage{jair}
\usepackage{theapa}

\input epsf %% at top of file
  
\jairheading{23}{2005}{245-297}{12/03}{03/05}
\ShortHeadings{Graduality in argumentation}
{Cayrol, Lagasquie-Schiex}
\firstpageno{245}
  

\newtheorem{defin}{Definition}
\newtheorem{theo}{Theorem}
\newtheorem{propriet}{Property}
\newtheorem{conseq}{Consequence}
\newtheorem{prop}{Proposition}
\newtheorem{regle}{Rule}
\newtheorem{lemme}{Lemma}
\newtheorem{nota}{Notation}
\newtheorem{ex}{Example}


\newcommand{\Nat}{\mathds{N}}

\newenvironment{preuve}{\begin{quote}{\bf Proof}\ \\}{\hfill$\Box$\\\end{quote}}
\newenvironment{preuveL}{\begin{quote}{\bf Proof}\ \\}{\hfill$\Box$\\\end{quote}}

\newenvironment{monitem}{\begin{list}{{\vrule width 3pt height 4pt depth -1pt}}{\setlength{\parsep}{0pt}\setlength{\partopsep}{0pt}\setlength{\itemsep}{2pt}}}{\end{list}}

\renewcommand{\labelitemi}{{\vrule width 3pt height 4pt depth -1pt}}
\renewcommand{\labelitemiii}{{\vrule width 2pt height 3pt depth -1pt}}
\newcommand{\entails}{{\,\mid\!\sim\,}}
\newcommand{\entailsnot}{{\,\mid\!\not\sim\,}}
\newcommand{\abo}{{\mathcal{A}}}
\newcommand{\gbo}{{\mathcal{G}}}
\newcommand{\lbo}{{\mathcal{L}}}
\newcommand{\cbo}{{\mathcal{C}}}
\newcommand{\rbo}{{\mathcal{R}}}
\newcommand{\tbo}{{\mathcal{T}}}
\newcommand{\ebo}{{\mathcal{E}}}
\newcommand{\vbo}{{\mathcal{V}}}
\newcommand{\impl}{{\to}}
\newcommand{\deb}{{<}}
\newcommand{\fin}{{>}}
\newcommand{\noexists}{{\not\exists}}
\newcommand{\ctt}{{{\tt C}}}
\newcommand{\AR}{{\deb\abo,\rbo\fin}}
\newcommand{\sort}{{\mbox{\tt Sort}}}


\def\tab{\hspace*{1cm}}
\def\cf{{\it cf.}}
\def\demitab{\hspace*{0.5cm}}

\def\bigtab{\hspace*{2cm}}

\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}

%*****************************************************************************
%\parskip 4pt plus 1pt
\parindent 0pt

%\pagestyle{empty}
%*****************************************************************************

\begin{document}

\title{\huge Graduality in Argumentation}

\author{\name Claudette Cayrol \email ccayrol@irit.fr \\
       \name Marie-Christine Lagasquie-Schiex \email lagasq@irit.fr \\
       \addr IRIT-UPS, 118 route de Narbonne\\
       31062 Toulouse Cedex, FRANCE}


\date{\ }

\maketitle


\begin{abstract}
  Argumentation is based on the exchange and valuation of interacting
  arguments, followed by the selection of the most acceptable of them
  (for example, in order to take a decision, to make a choice).
  Starting from the framework proposed by Dung in 1995, our purpose is
  to introduce ``graduality'' in the selection of the best arguments,
  {\it i.e.} to be able to partition the set of the arguments in more
  than the two usual subsets of ``selected'' and ``non-selected''
  arguments in order to represent different levels of selection.
  Our basic idea is that an argument is all the more acceptable if it
  can be preferred to its attackers.  First, we discuss general
  principles underlying a ``gradual'' valuation of arguments based on
  their interactions.  Following these principles, we define several
  valuation models for an abstract argumentation system.  Then, we
  introduce ``graduality'' in the concept of acceptability of
  arguments. We propose new acceptability classes and a refinement of
  existing classes taking advantage of an available ``gradual''
  valuation.
%The argumentation is based on the exchange and the valuation of interacting
%arguments, then on the selection of the ``best'' arguments (called
%acceptable arguments) in order to take a decision. Using the framework
%proposed by Dung in 1995, we consider two studies: one is based on
%different gradual valuations, and the other deals with different mechanisms of
%acceptability (some of these mechanisms will use the gradual valuations).
\end{abstract}


%\tableofcontents



%*****************************************************************************
%*****************************************************************************
\section{Introduction}\label{intro}
%*****************************************************************************
%*****************************************************************************

As shown by~\citeA{Dung95}, argumentation frameworks provide a unifying
and powerful tool for the study of several formal systems developed
for common-sense reasoning, as well as for giving a semantics to logic
programs.  Argumentation is based on the exchange and valuation of
interacting arguments which support opinions and assertions.  It can
be applied, among others, in the legal domain, for collective decision
support systems or for negotiation support.

The fundamental characteristic of an argumentation system is the
interaction between arguments. In particular, a relation of attack
may exist between arguments.  For example, if the argument takes the
form of a logical proof, arguments for a proposition and arguments
against this proposition can be advanced. In that case, the attack
relation relies on logical inconsistency.

The argumentation process is usually divided in two steps: a
\emph{valuation} of the relative strength of the arguments, followed
by the \emph{selection} of the most \emph{acceptable} arguments.
%There are different works showing the link between valuations and
%some semantics for the acceptability.
%(\cf~\citeA{}).

\bigskip

In the valuation step, it is usual to distinguish two different types
of valuations:
\begin{monitem}
\item \emph{intrinsic valuation}: here, the value of an argument is
  independent of its interactions with the other arguments. This
  enables to simply express to what extent an argument increases the
  confidence in the statement it supports (see~\citeR{Pollock92,KAEF95,Parsons97,PS97,AC98,KHB00,Pollock01}).
  
  For example, in the work of~\citeA{KAEF95}, using the following knowledge base,
  composed of {\it (formula, probability)}  pairs $\{(\phi_1,
  0.8)$, $(\phi_2, 0.8)$, $(\phi_3, 0.8)$, $((\phi_1 \land \phi_2 \to
  \phi_4), 1)$, $((\phi_1 \land \phi_3 \to \phi_4), 1)\}$, two
  arguments can be produced\footnote{Here, the 
    arguments are under the form of an ``Explanation-Conclusion
    Pair''. This is one possible way to compute arguments (see
    also~\citeR{LS89,Vreeswijk97,Pollock92,PS97,SL92,EFK93,KHB00,AC02a}).}:
  \begin{monitem}
  \item $A_1 = <\{\phi_1, \phi_2, (\phi_1 \land \phi_2 \to \phi_4)\},
    \phi_4>$
  \item and $A_2 = <\{\phi_1, \phi_3, (\phi_1 \land \phi_3 \to
    \phi_4)\}, \phi_4>$.
  \end{monitem}
  Both arguments have the same weight $0.8 \times 0.8 \times 1 =
  0.64$, and the formula $\phi_4$ has the weight $0.64 + 0.64 - 0.512
  = 0.768$\footnote{Weights being probabilities, the weight of an
    argument is the probability of the conjunction of the formulae of
    the argument, and the weight of $\phi_4$ is the probability of the
    disjunction of $A_1$ and $A_2$.}.
  
\item \emph{interaction-based valuation}: here the value of an
  argument depends on its attackers (the arguments attacking it), the
  attackers of its attackers (the defenders), etc.\footnote{Here, we
    consider only the interactions corresponding to attacks between
    arguments. There exist also some other types of interactions (for
    example, arguments which reinforce other arguments instead of
    attacking them, see~\citeR{KP01,Verheij02}).  For this kind of
    interaction, graduality has not been considered.}
  
  Several approaches have been proposed along this line
  (see~\citeR{Dung95,AC98,JV99,BH01}) which differ in the sets of
  values used. Usually, two values are considered.  However, there
  are very few proposals which use more than two values (three values
  in~\citeR{JV99}, and an infinity of values in~\citeR{BH01}).
  
  For example, in the work of~\citeA{BH01}, the set of values is the interval of
  the real line $[0,1]$. In this case, with the set of
  arguments\footnote{Here, the initial knowledge base is useless.}
  $\{A_1, A_2, A_3\}$ and considering that $A_1$ attacks $A_2$ which
  attacks $A_3$, the value of the argument $A_1$ (resp.  $A_2$, $A_3$)
  is $1$ (resp. $\frac{1}{2}$, $\frac{2}{3}$).
\end{monitem}

Intrinsic valuation and interaction-based valuation have often been
used separately, according to the considered applications. Some recent
works however consider a combination of both approaches
(see~\citeR{AC98,KP01,Pollock01}).

\bigskip

Considering now the selection of the more acceptable arguments, it is
usual to distinguish two approaches:
\begin{monitem}
\item \emph{individual acceptability}: here, the acceptability of
  \emph{an argument} depends only on its properties. For example, an
  argument can be said acceptable if and only if it does not have any
  attacker (in this case, only the interaction between arguments is
  considered, see~\citeR{EFK93}). In the context of an intrinsic
  valuation, an argument can also be said acceptable if and only if it
  is ``better'' than each of its attackers (see~\citeR{AC98}).
  
\item {\em collective acceptability}: in this case, the
  acceptability of a {\em set of arguments} is explicitly defined.
  For example, to be acceptable, a set of arguments may not contain
  two arguments such that one attacks the other (interactions between
  arguments are used).  \citeS{Dung95} framework is well suited for
  this kind of approach but allows only for a binary classification:
  the argument belongs or does not belong to an acceptable set.
\end{monitem}

\bigskip 

It is clear that except for \emph{intrinsic valuations}, most
proposals do not allow for any gradual notion of valuation or
acceptability ({\it i.e.}  there is a low number of levels to describe
values and the acceptability is usually binary). Our aim is therefore
to introduce graduality  in these two steps.

However, the processes of valuation and of selection are often linked
together.  This is the case when the selection is done on the basis of
the value of arguments\footnote{For example, using~\citeS{BH01}
  valuation, we can decide that all the arguments whose value is $>
  0.5$ are selected, because $0.5$ is the mean value of the set of
  values; Another possibility, with different valuations
  (interaction-based or intrinsic), is to accept an argument when its
  value is better than the value of each of its attackers.} or when
the selection defines a binary valuation on arguments. We will
therefore:
\begin{monitem} 
\item first consider and discuss the general principles
  concerning the definition of a \emph{gradual interaction-based
    valuation} and then define some valuation models in an abstract
  argumentation system,
\item then, introduce the notion of \emph{graduality in the definition
    of the acceptability} using the previously defined gradual
  valuations, but also some more classical mechanisms.
\end{monitem}

Some graduality has already been introduced in argumentation systems.
For instance, in the work of~\citeA{Pollock01}, degrees of justification for
beliefs are computed. Arguments are sequences of conclusive and/or
{\it prima-facie} inferences. Arguments are collected in a graph where
a node represents the conclusion of an argument, a support link ties a
node to nodes from which it is inferred, and an attack link indicates
an attack between nodes. The degree of justification of a belief is
computed from the strength of the arguments concluding that belief and
the strength of the arguments concluding on an attacker of the belief.

Our work takes place in a more abstract framework since we do not 
consider any argument structure.  Our valuation models are based on 
interactions between arguments and directly apply to arguments.

We use the framework defined by~\citeA{Dung95}: a set of arguments and
a binary attack relation between arguments. We also use a graphical
representation of argumentation systems (see Section~\ref{dung}).  The
gradualisation of interaction-based valuations will be presented in
Section~\ref{eval-grad}.  Then, in Section~\ref{acceptabilite}, we
will consider different mechanisms leading to gradual acceptability,
sometimes relying on the gradual valuations defined in
Section~\ref{eval-grad}.  We will conclude in
Section~\ref{conclusion}.

All the proofs of the properties stated in Sections~\ref{eval-grad}
and~\ref{acceptabilite} will be given in Appendix~\ref{annexe}.

%*****************************************************************************
\section{\citeS{Dung95} framework  and its graphical representation}
%*****************************************************************************
\label{dung}\label{def-gen-dung}


We consider the abstract framework introduced by~\citeA{Dung95}.
An \emph{argumentation system} $\AR$ is a set $\abo$ of
arguments and a binary relation $\rbo$  on $\abo$ called an
\emph{attack relation}: consider $A_i$ and $A_j\in \abo$, $A_i \rbo
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 \rbo$).

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

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

\paragraph{Notation:}
$\AR$ defines a directed graph $\gbo$ called the \emph{attack graph}.
Consider $A \in \abo$, the set $\rbo^-(A)$ is the set of the arguments
attacking $A$\footnote{$\rbo^-(A) = \{A_i \in \abo | A_i \rbo A\}$.}
and the set $\rbo^+(A)$ is the set of the arguments attacked by
$A$\footnote{$\rbo^+(A) = \{A_i \in \abo | A \rbo A_i\}$.}.

\begin{ex}\label{ex0}\  \\
  The system $\deb\abo = \{ A_1, A_2, A_3, A_4\}, \rbo = \{(A_2, A_3),
  (A_4, A_3), (A_1, A_2)\}\fin$ defines the following graph $\gbo$
  with the root\footnote{The word ``root'' is used in an informal
    sense (it just means that there are in the graph some paths
    leading to this node). This term and other terms (leaf, branch,
    path, \ldots) which are used in this document are standard in
    graph theory but may have a different definition. They are usual
    terms in the argumentation domain. Please see 
    Definition~\ref{def-dung} in order to know their precise meaning
    in this document. These definitions simply take into account the
    fact that the directed edges of our graph link attackers to
    attacked argument).} $A_3$:\\

  \centerline{\includegraphics[scale=0.8]{ex-graphe}}
\end{ex}

\begin{defin}[Graphical representation of an argumentation system]\label{def-dung}
  Let $\gbo$ be the attack graph associated with the argumentation
  system $\AR$, we define:

  \begin{description}
  \item[Leaf of the attack graph] A {\em leaf of $\gbo$} is an
    argument $A \in \abo$ without attackers\footnote{$A$ is a leaf iff
      $\rbo^-(A) = \varnothing$.}.
    
  \item[Path in the attack graph] A \emph{path from $A$ to $B$} is a
    sequence of arguments $\cbo = A_1-\ldots-A_n$ such that:
    \begin{monitem}
    \item $A=A_1$,
    \item $A_1 \rbo A_2$,
    \item \ldots,
    \item $A_{n-1} \rbo A_n$,
    \item $A_n = B$.
    \end{monitem}
    The \emph{length of the path} is $n-1$ (the number of edges that
    are used in the path) and will be denoted by $l_{\cbo}$.
    
    A special case is the path\footnote{We will assume that there
      exists an infinity of such paths. This assumption greatly
      simplifies the handling of leaves later in the paper.} from $A$
    to $A$ whose length is $0$.
    
    The set of paths from $A$ to $B$ will be denoted by $\cbo(A,
    B)$.
    

  \item[Dependence, independence, root-dependence of a path]\ \\
    Consider 2 paths $\cbo_A \in \cbo(A_1, A_n)$ and $\cbo_B \in
    \cbo(B_1, B_m)$.
    
    These two paths will be said \emph{dependent} iff $\exists A_i \in
    \cbo_A$, $\exists B_j \in \cbo_B$ such that $A_i = B_j$. Otherwise
    they are {\em independent}.
    
    These two paths will be said \emph{root-dependent in $A_n$} iff
    $A_n = B_m$ and $\forall A_i \neq A_n \in \cbo_A$, $\noexists B_j
    \in \cbo_B$ such that $A_i = B_j$.
    
  \item[Cycles in the attack graph] A {\em cycle}\footnote{This
      definition of a cycle corresponds to the definition of an
      elementary cycle in graph theory (an elementary cycle does not
      contain 2 edges with the same initial extremity, or the same
      ending extremity).} is a path $\cbo= 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 $\cbo$ is {\em isolated} iff $\forall A \in \cbo$,
    $\not\exists B \in \abo$ such that $B \rbo A$ and $B \not\in
    \cbo$.
    
    Two cycles $\cbo_A = A_1-\ldots-A_n-A_1$ and $\cbo_B =
    B_1-\ldots-B_m-B_1$ are \emph{interconnected} iff $\exists i \in
    [1,n], \exists j \in [1,m]$ such that $A_i = B_j$.
\end{description}
\end{defin}

We use the notions of direct and indirect attackers and defenders. The
notions introduced here are inspired by related definitions first
introduced by~\citeA{Dung95} but are not strictly
equivalent\footnote{In~\citeS{Dung95} work, direct attackers (resp.
  defenders) are also indirect attackers (resp. defenders) which is
  not true in our definitions.}.

\begin{defin}[Direct/Indirect Attackers/Defenders of an argument]
  Consider $A \in \abo$:
  \begin{monitem}
  \item The \emph{direct attackers} of $A$ are the elements of
    $\rbo^-(A)$.
  \item The \emph{direct defenders} of $A$ are the direct attackers of
    the elements of $\rbo^-(A)$.
  \item The \emph{indirect attackers} of $A$ are the elements $A_i$
    defined by:
    
    \centerline{$\exists \cbo \in \cbo(A_i,A)$ such that $l_{\cbo} =
      2k+1$, with $k \geq 1$.}
  \item the \emph{indirect defenders} of $A$ are the elements $A_i$
    defined by:
  
    \centerline{$\exists \cbo \in \cbo(A_i,A)$ such that $l_{\cbo} =
      2k$, with $k \geq 2$.}
  \end{monitem}
\end{defin}

If the argument $A$ is an attacker (direct or indirect) of the
argument $B$, we say that $A$ {\em attacks} $B$ (or that $B$ \emph{is
  attacked by} $A$). In the same way, if the argument $A$ is a
defender (direct or indirect) of the argument $B$, then $A$ {\em
  defends} $B$ (or $B$ \emph{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.

\begin{defin}[Attack branch and defence branch of an argument]
  Consider $A \in \abo$, an \emph{attack branch} (resp. \emph{defence
    branch}) for $A$ is a path in $\gbo$ from a leaf to $A$ whose
  length is odd (resp. even). We say that $A$ is the \emph{root of an
    attack branch} (resp. \emph{a defence branch}).
\end{defin}

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:

\begin{ex}\label{ex1}\ \\
  \begin{center}
    \begin{tabular}{c l}
      \begin{minipage}{3.5cm}

        \includegraphics[scale=0.6]{ex-notionsbis.eps}
      \end{minipage}&
      \begin{minipage}{11cm}
        On this graph $\gbo$, we can see:
        \begin{monitem}
        \item a path from $C_2$ to $A$ whose length is 2
          ($C_2-B_1-A$),
        \item 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),
        \item the two previous cycles are interconnected (in $A_1$ and
          $A_3$),
        \item 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,
        \item $D_1$, $C_2$, $E_1$ are the leaves of $\gbo$,
        \item $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,
        \item $C_2$, $B_1$ and $B_2$ are the direct attackers of $A$,
        \item $C_1$, $C_2$ (which is already a direct attacker of $A$)
          and $C_3$ are the direct defenders of $A$,
        \item $D_1$ and $D_2$ are the two indirect attackers of $A$,
        \item $E_1$ is the only indirect defender of $A$.
        \end{monitem}
      \end{minipage}
\end{tabular}
\end{center}
\end{ex}


%*****************************************************************************
%*****************************************************************************
%*****************************************************************************
\section{Graduality in interaction-based valuations}\label{eval-grad}
%*****************************************************************************
%*****************************************************************************
%*****************************************************************************

We consider two different valuation methods for taking into account
the quality of attackers and defenders of an argument in order to
define the value of an argument using only the interaction between
arguments\footnote{We pursue a work initiated in~\cite{CLS03c} and
  propose some improvements.}:

\begin{monitem}
\item In the first approach, the value of an argument only depends on
  the values of the direct attackers of this argument. Therefore,
  defenders are taken into account through the attackers. This
  approach is called {\em local}.
  
\item In the second approach, the value of an argument represents the
  set of all the attack and the defence branches for this argument.
  This approach is called {\em global}.
\end{monitem}

The main difference between these two approaches is illustrated by the
following example:

\centerline{\includegraphics[scale=0.75]{compar-loc-glo.eps}}

In the local approach, $B$ has two direct attackers ($C_2$ and $C_1$)
whereas $B'$ has only one ($C'$). Thus $B'$ is better than $B$ (since
$B'$ suffers one attack whereas $B$ suffers two attacks).

In the global approach, two branches (one of attack and one of
defence) lead to $B$ whereas only one branch of attack leads to $B'$.
Thus $B$ is better than $B'$ (since it has at least one defence
whereas $B'$ has none). In this case, $C_1$ loses its negative status
of attacker, since it is in fact ``carrying a defence'' for $B$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Local approach (generic valuation)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Local approach (generic valuation)}
\label{app1}

Some existing proposals can already be considered as examples of
\emph{local valuations}. 

\bigskip

In~\citeS{JV99} approach, a labelling of a
set of arguments assigns a status (accepted, rejected, undecided) to
each argument using labels from the set $\{+, -, ?\}$. $+$ (resp. $-$,
$?$) represents the ``accepted'' (resp. ``rejected'', ``undecided'')
status.  Intuitively, an argument labelled with $?$ is both supported
and weakened.

\begin{defin}[Jakobovits and Vermeir's labellings, 1999]
  Let $\deb\abo, \rbo\fin$ be an argumentation system. A complete
  labelling of $\deb\abo, \rbo\fin$ is a function $Lab~: \abo \to \{+,
  ?, -\}$ such that:
  \begin{enumerate}
  \item\label{c1} If $Lab(A) \in \{ ?, -\}$ then $\exists B \in
    \rbo^-(A)$ such that $Lab(B) \in \{+, ?\}$
  \item\label{c2} If $Lab(A) \in \{+, ?\}$ then $\forall B \in
    \rbo^-(A) \cup \rbo^+(A)$, $Lab(B) \in \{ ?, -\}$
%\item\label{c2} If $Lab(A) \in \{+, ?\}$ then     $\forall B \in \rbo^-(A)$, $Lab(B) \in \{ ?, -\}$ et
%$\forall C \in  \rbo^+(A)$, $Lab(C) \in \{ ?, -\}$
  \end{enumerate}
\end{defin}

The underlying intuition is that an argument can only be weakened
(label $-$ or $?$) if one of its direct attackers is supported
(condition~\ref{c1}); an argument can get a support only if all its
direct attackers are weakened and an argument which is supported
(label $+$ or $?$) weakens the arguments it attacks
(condition~\ref{c2}).  So:
\begin{monitem}
\item If $A$ has no attacker $Lab(A) = +$.
\item If $Lab(A) = ?$ then  $\exists B \in  \rbo^-(A)$ such that $Lab(B) = ?$.
\item If ($\forall B \in   \rbo^-(A)$, $Lab(B) = -$) then $Lab(A) = +$.
\item If $Lab(A) = +$ then $\forall B \in \rbo^-(A) \cup \rbo^+(A)$, $Lab(B) = -$.
%\item If $Lab(A) = +$ then      $\forall B \in \rbo^-(A)$, $Lab(B) = -$ et
%$\forall C \in  \rbo^+(A)$, $Lab(C) = -$.
\end{monitem}

Every argumentation system can be completely labelled. The associated
semantics is that $S$ is an acceptable set of arguments iff there
exists a complete labelling $Lab$ of $\deb\abo, \rbo\fin$ such that $S
= \{A | Lab(A) = +\}$.

Other types of labellings are introduced by~\citeA{JV99} among which
the so-called ``rooted labelling'' which induces a corresponding
``rooted'' semantics. The idea is to  reject only the arguments attacked by
accepted arguments: an attack by an ``undecided'' argument is not
rooted since an ``undecided'' attacker may become rejected.

\begin{defin}[Jakobovits and Vermeir's labellings, 1999 -- continuation] \ \\
The complete labelling $Lab$ is rooted iff  $\forall A \in
  \abo$, if $Lab(A) = -$ then $\exists B \in \rbo^-(A)$ such that
  $Lab(B) = +$.
\end{defin}

The rooted semantics enables to clarify the links between all the
other semantics introduced by~\citeA{JV99} and some semantics
introduced by~\citeA{Dung95}.

%More generally, one proved:
%\begin{monitem}
%\item In the directed acyclic graph case, every argument is labelled by
%  $+$ or $-$.  An argument $A$ is accepted iff it is (indirectly)
%  defended against each of its direct attackers (i.e., iff each of its
%  direct attackers is rejected).  
%\item In the case of a graph with cycle: the
%  arguments that appear on an odd length cycle are necessarily
%  labelled by ``undecided''. If $Lab$ is a rooted labelling:
%  \begin{monitem}
%  \item $A$ is accepted ($+$) iff all its direct attackers are
%    rejected ($-$).
%  \item $A$ is rejected iff one of its direct attackers is accepted.
%  \item $A$ is undecided iff one of its direct attackers is undecided
%    and none of its direct attackers is accepted.
%  \end{monitem}
%\end{monitem} 

\begin{ex}\label{ex-1-branche}
On the following example:

      \centerline{\includegraphics[scale=0.6]{ex4bis.eps}}

For $n$ even, we obtain $Lab(A_n) = Lab(A_{n-2}) = \ldots = Lab(A_2) = +$ and
  $Lab(A_{n-1}) = Lab(A_{n-3}) = \ldots = Lab(A_1) = -$. 

For $n$ odd, we obtain $Lab(A_n) = Lab(A_{n-2}) = \ldots = Lab(A_1) = +$ and
  $Lab(A_{n-1}) = Lab(A_{n-3}) = \ldots = Lab(A_2) = -$
\end{ex}

\bigskip

Another type of \emph{local valuation} has been introduced recently
by~\citeA{BH01} for ``deductive'' arguments.  The approach can be 
characterised as follows.  An argument is structured as a pair
$\langle\textit{support},\textit{conclusion}\rangle$, where
\textit{support} is a consistent set of formulae that enables to prove
the formula \textit{conclusion}.  The attack relation considered here
is strict and cycles are not allowed.  The notion of a ``tree of
arguments'' allows a concise and exhaustive representation of
attackers and defenders of a given argument, root of the tree.  A
function, called a ``categoriser'', assigns a value to a tree of
arguments. This value represents the relative strength of an argument
(root of the tree) given all its attackers and defenders.  Another
function, called an ``accumulator'', synthesises the values assigned
to all the argument trees whose root is an argument for (resp.
against) a given conclusion.
The phase of categorisation therefore corresponds to an interaction-based
valuation. \citeA{BH01} introduce the following function $Cat$:

\small
\begin{monitem}
\item if $\rbo^-(A) = \varnothing$, then $Cat(A) = 1$
\item if $\rbo^-(A) \neq \varnothing$ with $\rbo^-(A) = \{A_1, \ldots, A_n\}$,
  $Cat(A) = \frac{1}{1 + Cat(A_1) + \ldots + Cat(A_n)}$
\end{monitem} 
\normalsize

Intuitively, the larger the number of direct attackers of an argument,
the lower its value. The larger the number of defenders of an
argument, the larger its value.

\paragraph{Example~\ref{ex-1-branche} (continuation)} {\it
We obtain:

$Cat(A_n) = 1$, $Cat(A_{n-1}) = 0.5$, $Cat(A_{n-2}) = 0.66$, $Cat(A_{n-3}) =
0.6$, \ldots, and $Cat(A_1) = (\sqrt{5} - 1)/2$ when $n \to \infty$
(this value is the inverse of the golden ratio\footnote{The golden ratio is a famous
  number since the antiquity which has several interesting properties
  in several domains (architecture, for example).}).

So, we have:

If $n$ is even $Cat(A_{n-1}) \leq \ldots \leq Cat(A_3) \leq Cat(A_1) \leq Cat(A_2)
\leq \ldots \leq Cat(A_n) = 1$

If $n$ is odd $Cat(A_{n-1}) \leq \ldots \leq Cat(A_2) \leq Cat(A_1) \leq
Cat(A_3) \leq \ldots \leq Cat(A_n) = 1$ 
}


\bigskip

Our approach for \emph{local valuations} is a generalisation of these
two previous proposals in the sense that~\citeS{BH01} $Cat$ function
and~\citeS{JV99} labellings are instances of our approach.

The main idea is that the value of an argument is obtained with the
composition of two functions:
\begin{monitem}
\item one for aggregating the values of all the direct attackers of
  the argument; so, this function computes the value of the ``direct
  attack'';
\item the other for computing the effect of the ``direct attack'' on
  the value of the argument: if the value of the ``direct attack''
  increases then the value of this argument decreases, if the value of
  the ``direct attack'' decreases then the value of this argument
  increases.
\end{monitem}

Let $(W,\geq)$ be a totally ordered set with a minimum element
($V_{\mbox{\scriptsize Min}}$) and a subset $V$ of $W$, that contains
$V_{\mbox{\scriptsize Min}}$ and with a maximum element
$V_{\mbox{\scriptsize Max}}$.

\begin{defin}[Generic gradual valuation]\label{def-eval-generique} 
  Let $\deb\abo, \rbo\fin$ be an argumentation system. A valuation is
  a function $v: \abo \to V$ such that:

  \begin{enumerate}
  \item  $\forall A \in \abo$, $v(A) \geq V_{\mbox{\scriptsize Min}}$
  \item  $\forall A \in \abo$, if $\rbo^-(A) = \varnothing$, then $v(A)
    = V_{\mbox{\scriptsize Max}}$  
  \item $\forall A \in \abo$, if $\rbo^-(A) = \{A_1, \ldots, A_n\}
    \neq \varnothing$, then $v(A) = g( h (v(A_1),\ldots, v(A_n)))$
  \end{enumerate}
  
  with $h: V^* \to W$ such that ($V^*$ denotes the set of all finite
  sequences of elements of $V$)
  \begin{monitem}
  \item $h(x) = x$
  \item $h () = V_{\mbox{\scriptsize Min}}$
  \item For any permutation $(x_{i1}, \ldots, x_{in})$ of $(x_1,
    \ldots, x_n)$, $h(x_{i1}, \ldots, x_{in}) = h(x_1, \ldots, x_n)$
  \item   $h(x_1, \ldots, x_n, x_{n+1}) \geq h(x_1, \ldots, x_n)$
  \item  if $x_i \geq x'_i$ then $h(x_1, \ldots, x_i, \ldots, x_n)
    \geq h(x_1, \ldots, x'_i, \ldots, x_n)$
  \end{monitem}
  and $g: W \to V$ such that
  \begin{monitem}
  \item    $g(V_{\mbox{\scriptsize Min}}) = V_{\mbox{\scriptsize Max}}$
  \item   $g(V_{\mbox{\scriptsize Max}}) < V_{\mbox{\scriptsize Max}}$
  \item   $g$ is non-increasing  (if $x \leq y$ then $g(x) \geq g(y)$)
  \end{monitem}
\end{defin}


Note that $h(x_1, \ldots, x_n) \geq \max (x_1,\ldots, x_n)$ is a
logical consequence of the properties of the function $h$.

A first property on the function $g$ explains the behaviour of the
local valuation in the case of an argument which is the root of only
one branch (like in Example~\ref{ex-1-branche}):

\begin{propriet}\label{prop-de-g} 
  The function $g$ satisfies for all $n \geq 1$:
  $$g(V_{\mbox{\scriptsize Max}}) \leq g^3(V_{\mbox{\scriptsize Max}})
  \leq \ldots \leq g^{2n+1}(V_{\mbox{\scriptsize Max}})\leq
  g^{2n}(V_{\mbox{\scriptsize Max}}) \leq \ldots \leq
  g^2(V_{\mbox{\scriptsize Max}}) \leq V_{\mbox{\scriptsize Max}}$$
  Moreover, if $g$ is strictly non-increasing and
  $g(V_{\mbox{\scriptsize Max}}) > V_{\mbox{\scriptsize Min}}$, the
  previous inequalities become strict.
\end{propriet}

A second property shows that the local valuation induces an ordering
relation on arguments:

\begin{propriet}[Complete preordering]\label{prop-pre-ordre-total}
  Let $v$ be a valuation in the sense of 
  Definition~\ref{def-eval-generique}. $v$ induces a
  complete\footnote{A complete preordering on $\abo$ means that any
    two elements of $\abo$ are comparable.}
  preordering $\succeq$ on the set of arguments $\abo$ defined by: $A
  \succeq B$ iff $v(A) \geq v(B)$.
\end{propriet}

A third property handles the cycles:

\begin{propriet}[Value in a cycle]\label{prop-val-circuit}
  Let $\cbo$ be an isolated cycle of the attack graph, whose length is
  $n$. If $n$ is odd, all the arguments of the cycle have the same
  value and this value is a fixpoint of the function $g$. If $n$ is
  even, the value of each argument of the cycle is a fixpoint of the
  function $g^n$.
\end{propriet}

The following property shows the underlying principles satisfied by
all the local valuations defined according to our schema:

\begin{propriet}[Underlying principles]\label{prop-principes-eval-loc}
  The gradual valuation given by 
  Definition~\ref{def-eval-generique} respects the following
  principles:

  \begin{description}
  \item[{\bf P1}] The valuation is maximal for an argument without
    attackers and non maximal for an attacked and undefended argument.
  \item[{\bf P2}] The valuation of an argument is a function of the
    valuation of its direct attackers (the ``direct attack'').
  \item[{\bf P3}] The valuation of an argument is a non-increasing
    function of the valuation of the ``direct attack''.
  \item[{\bf P4}] Each attacker of an argument contributes to the
    increase of the valuation of the ``direct attack'' for this
    argument.
\end{description}
\end{propriet}


The last properties explain why~\citeA{JV99} and~\citeA{BH01} propose instances of the
local valuation described in Definition~\ref{def-eval-generique}:

\begin{propriet}[Link with~\citeR{JV99}]\label{prop-lien-JV99}\ \\
  Every rooted labelling of $\deb\abo, \rbo\fin$ in the sense
  of~\citeA{JV99} can be defined as an instance of the generic
  valuation such that:
  \begin{monitem}
  \item $V = W = \{-, ?, +\}$ with $- <\ ? < +$,
  \item $V_{\mbox{\scriptsize Min}} = -$, 
  \item $V_{\mbox{\scriptsize Max}} = +$,
  \item $g$ defined by $g(-) = +$, $g(+) = -$, $g( ?) = ?$ 
  \item and $h$ is the function $\max$.
  \end{monitem}
\end{propriet}


\begin{propriet}[Link with~\citeR{BH01}]\label{prop-lien-BH01}
  The gradual valuation of~\citeA{BH01} can be defined as an instance
  of the generic valuation such that:
  \begin{monitem}
  \item $V = [0,1]$, 
  \item $W = [0, \infty[$, 
  \item $V_{\mbox{\scriptsize Min}} = 0$,
  \item $V_{\mbox{\scriptsize Max}} = 1$, 
  \item $g: W \to V$ defined by $g(x) = \frac{1}{1 + x}$
  \item and $h$ defined by $h(x_1, \ldots, x_n) = x_1 + \ldots + x_n$.
  \end{monitem}
\end{propriet}

Note that, in the work of~\citeA{BH01}, the valued graphs are acyclic. However, it
is easy to show that the valuation proposed by~\citeA{BH01} can be
generalised to graphs with cycles (in this case, we must solve second
degree equations -- see Example~\ref{ex2}).

\begin{ex}\label{ex} Consider the following graph:

\centerline{\includegraphics[scale=0.6]{autrexemple.eps}}


In this example, with the generic valuation, we obtain:


\begin{monitem}
\item $v(E_1) = v(D_2) = v(D_3) = v(C_4) = v(B_4) =
  V_{\mbox{\scriptsize Max}}$
\item $v(D_1) = v(C_2) = v(C_3) = v(B_3) = g(V_{\mbox{\scriptsize
      Max}})$
\item $v(C_1) = v(B_2) = g^2(V_{\mbox{\scriptsize Max}})$
\item $v(B_1) = g(h(g^2(V_{\mbox{\scriptsize Max}}),
  g(V_{\mbox{\scriptsize Max}})))$
\item $v(A) = g(h(g(h(g^2(V_{\mbox{\scriptsize Max}}),
  g(V_{\mbox{\scriptsize Max}}))), g^2(V_{\mbox{\scriptsize Max}}),
  g(V_{\mbox{\scriptsize Max}}), V_{\mbox{\scriptsize Max}}))$ 
\end{monitem}

So, we have: 

\centerline{$E_1, D_2, D_3, C_4, B_4$}

\centerline{$\succeq$}

\centerline{$C_1, B_2$}

\centerline{$\succeq$}

\centerline{$D_1, C_2, C_3, B_3$}

However, the constraints on $v(A)$ and $v(B_1)$ are insufficient to
compare $A$ and $B_1$ with the other arguments.

The same problem exists if we reduce the example to the hatched part
of the graph in the previous figure; we obtain $E_1, D_2 \succeq C_1
\succeq D_1, C_2$, but $A$ and $B_1$ cannot be compared with the other
arguments\footnote{$v(A) = g^2(h(g^2(V_{\mbox{\scriptsize Max}},
  g(V_{\mbox{\scriptsize Max}})))$ and $v(B_1) =
  g(h(g^2(V_{\mbox{\scriptsize Max}}), g(V_{\mbox{\scriptsize
      Max}})))$.}.


Now, we use the instance of the generic valuation
proposed by~\citeA{BH01}:


\begin{monitem}
\item $v(E_1) = v(D_2) = v(D_3) = v(C_4) = v(B_4) = 1$,
\item $v(D_1) = v(C_2) = v(C_3) = v(B_3) = \frac{1}{2}$,
\item $v(C_1) = v(B_2) = \frac{2}{3}$,
\item $v(B_1) = \frac{6}{13}$,
\item $v(A) = \frac{78}{283}$.
\end{monitem}

So, we have:

\centerline{$E_1, D_2, D_3, C_4, B_4$}

\centerline{$\succeq$}

\centerline{$C_1, B_2$}

\centerline{$\succeq$}

\centerline{$D_1, C_2, C_3, B_3$}

\centerline{$\succeq$}

\centerline{$B_1$}

\centerline{$\succeq$}

\centerline{$A$}


However, if we reduce the example to the hatched part of the graph,
then the value of $A$ is $\frac{13}{19}$. So, $v(A)$ is better than
$v(B_1)$ and $v(D_1)$, but also than $v(C_1)$ ($A$ becomes better than
its defender).
\end{ex}



\begin{ex}[Isolated cycle]\label{ex2}
Consider the following graph reduced to an isolated cycle:

\begin{center}
  \includegraphics[scale=0.7]{cas10.eps}.
\end{center}

A generic valuation gives $v(A) = v(B) =$ fixpoint of $g^2$. 

If we use the instance proposed by~\citeA{BH01}, $v(A)$ and $v(B)$
are solutions of the following second degree equation: $x^2 + x - 1 = 0$. 

So, we obtain: $v(A) = v(B) = \frac{-1 +
  \sqrt{5}}{2} \approx 0.618$ (the
inverse of the golden ratio again).
\end{ex}


 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Global approach (with tuples)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Global approach (with tuples)}
\label{etiq-tuple}
\label{tuples}

We now consider a
second approach for the valuation step, called the global approach. Here, the
key idea is that the value of $A$ must describe the subgraph whose
root is $A$.  So, we want to memorise the length of each branch
leading to $A$ in a tuple (for an attack branch, we have an odd
integer, and for a defence branch, we have an even integer).

In this approach, the main constraint is that we must be able to
identify the branches leading to the argument and to compute their
lengths.  This is very easy in the case of an acyclic graph. We
therefore introduce first a global gradual valuation for acyclic
graphs.  Then, in the next sections, we extend our proposition to the
case of graphs with cycles, and we study the properties of this global
gradual valuation.



%*****************************************************************************
%*****************************************************************************
\subsubsection{Gradual valuation with tuples for acyclic graphs}
\label{val-tuple-acyclic}
%*****************************************************************************
%*****************************************************************************

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:

\begin{defin}[Tuple]\label{def-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}$.
\end{defin}

\begin{nota}
  $\tbo$ denotes the set of the tuples built with positive integers.
\end{nota}


\begin{defin}[Operations on the tuples]\label{oper-tuple}
  We have two kinds of operations on tuples:
  \begin{monitem}
  \item the concatenation of two tuples is defined by the function
    $\star: \tbo \times \tbo \to \tbo$ such that
  \begin{eqnarray*}
  0^{\infty} \star t = t \star 0^{\infty} & = & t \mbox{ for } t \neq ()\\
  (x_1, \ldots, x_n, \ldots) \star (x'_1, \ldots, x'_n, \ldots) & = &
\sort(x_1, \ldots,
  x_n, \ldots,x'_1, \ldots, x'_n, \ldots)
\end{eqnarray*}
$\sort$ being the function which orders a tuple by increasing values.

\item the addition of a tuple and an integer is defined by the
  function $\oplus: \tbo \times \Nat \to \tbo$ such that
  \begin{eqnarray*}
  0^{\infty} \oplus k & = & (k)\\
  () \oplus k & = & ()\\
  (x_1, \ldots, x_n) \oplus k & = & (x_1 + k, \ldots, x_n + k)\\
  (x_1, \ldots, x_n, \ldots) \oplus k & = & (x_1 + k, \ldots, x_n + k,
  \ldots) \mbox{ if } (x_1, \ldots, x_n, \ldots) \neq 0^{\infty}
\end{eqnarray*}
\end{monitem}
\end{defin}

Note that we allow infinite tuples, among other reasons, because they
are needed later in order to compute the ordering
relations described in Section~\ref{compar-val-tuple} (in particular
when the graph is cyclic).

The operations on the tuples have the following properties:

\begin{propriet}[Properties of $\star$ and $\oplus$]\label{comm-assoc}\ \\
  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}$\footnote{Otherwise it is false :
$(0^{\infty} \star (p)) \oplus k = (p + k)$,
whereas $(0^{\infty} \oplus k) \star ((p) \oplus k) = (k) \star (p + k) =
(k, p + k)$.},
$(t \star t') \oplus k = (t \oplus k) \star (t' \oplus k)$.

\end{propriet}

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:

\begin{defin}[Tupled value]\label{def-val-tuple}
  A {\em tupled value} is a pair of tuples $vt = [vt_p, vt_i]$ with:
\begin{monitem}
\item $vt_p$ is a tuple of even integers ordered by increased values;
  this tuple is called the even component of $vt$;
\item $vt_i$  is a tuple of odd integers ordered by increased values;
  this tuple is called the odd component of $vt$.
\end{monitem}
\end{defin}


\begin{nota}
  $\vbo$ denotes the subset of $\tbo \times \tbo$ of all tupled values
  (so, $\forall vt \in \vbo$, $vt$ is a pair of tuples satisfying
  Definition~\ref{def-val-tuple}).
\end{nota}


Using this notion of tupled-values, we can define the {\em computation
  process} of the gradual valuation with tuples\footnote{This
  definition is different from the definition given in~\cite{CLS03c}.
  The ideas are the same but the formalisation is different.} in the
case of acyclic graphs.

\begin{defin}[Valuation with tuples for acyclic
graphs]\label{def-nelle-eval-tuple}
  Let $\AR$ be an argumentation system without cycles. A valuation
  with tuples is a function $v: \abo \to \vbo$ such that:

  \begin{quote}
    If $A \in \abo$ is a leaf then

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

    If $A \in \abo$ has direct attackers denoted by  $B_1$, \ldots, $B_n$,
\ldots  then

\begin{center}
$v(A) = [v_p(A), v_i(A)]$ with:
\hspace*{0.1cm}\vrule\hspace*{0.1cm}\begin{minipage}{7cm}
$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 $
\end{minipage}
\end{center}
  \end{quote}
\end{defin}


\paragraph{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
both\footnote{The proof is the following:.
\begin{monitem}
\item If $A$ is not a leaf, at least one of the tuples is not empty,
  because there exists at least one branch whose length is $> 0$
  leading to $A$ (see Definitions~\ref{oper-tuple}
  and~\ref{def-nelle-eval-tuple}).
\item And, if $A$ is a leaf, there also exists at least one defence
  branch because the path from $A$ to $A$ is allowed and its length is
  $0$ (in fact, there are an infinity of such paths -- see
  Definition~\ref{def-dung}) and no attack branch leading to the leaf
  (see Definition~\ref{def-nelle-eval-tuple}).
\end{monitem}
So, the value of a leaf is $[0^{\infty},()]$, and it is impossible
that $v_p(A) = v_i(A) = ()$.}.

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).

\begin{ex}\label{ex-acyclic-graph} On this graph, the valuation with
  tuples gives the following results:

\begin{center}
\begin{tabular}{c l}
\begin{minipage}{3.5cm}
  \includegraphics[scale=0.6]{ex-notionster.eps}
\end{minipage}&
\begin{minipage}{8cm}
  On this graph $\gbo$, we have:
\begin{monitem}
\item $v(D_1) = v(C_2) = v(E_1) = [0^{\infty},()]$,
\item $v(C_1) = v(D_2) = [(),(1)]$,
\item $v(C_3) = [(2),()]$,
\item $v(B_1) = [(2),(1)]$,
\item $v(B_2) = [(),(3)]$,
\item $v(A) = [(2,4),(1,3)]$.
\end{monitem}
\end{minipage}
\end{tabular}
\end{center}
\end{ex}


%*****************************************************************************
%*****************************************************************************
\subsubsection{Study of cycles}
\label{study-cycle}
%*****************************************************************************
%*****************************************************************************

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~\ref{ex2} and ~\ref{ex2bis}), and when this notion is
useful, the length of a branch can be defined in different ways.

Let us consider different examples:

\begin{ex}[Unattacked cycle]\label{ex2bis}
  The graph is reduced to an unattacked cycle $A-B-A$ which attacks
  the argument C:

\centerline{\includegraphics[scale=0.7]{cas10bis.eps}}

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

There are two possibilities:
\begin{monitem}
\item First, one can consider that the cycle is like an infinite
  branch; so $A$ (resp.  $B$) is the root of one branch whose length
  is $\infty$. 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.

\item The second possibility is to consider that the cycle is like an
  infinity of branches; so $A$ (resp.  $B$) is the root of an
  infinity of attack branches and defence branches whose lengths are
  known and finite.
\end{monitem}

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:


\begin{center}
  \includegraphics[scale=0.75]{cas10-trad.eps}
\end{center}

The $A_i$ and $B_i$ must be new arguments created during the rewriting
process of the cycle.
\end{ex}

\begin{ex}[Attacked cycle]\label{ex2-nelle}
  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$):

\centerline{\includegraphics[scale=0.7]{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~\ref{ex2bis}, 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:

\centerline{\includegraphics[scale=0.7]{ex-circuit2-trad2.eps}}

The $A_i$ and $B_i$ must be new arguments created during the rewriting
process of the graph.
\end{ex}

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~\ref{def-nelle-eval-tuple} 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:

\begin{defin}[Rewriting of an unattacked cycle]\label{rewrite-unattack-cyc}
  Let $\cbo= A_0-A_1-\ldots-A_{n-1}-A_0$ an unattacked cycle. The graph
$\gbo$
  which contains $\cbo$ is rewritten as follows:
  \begin{enumerate}
  \item the cycle $\cbo$ is removed,
  \item and replaced by the infinite acyclic graphs, one for each
    $A_i$, $i= 0 \ldots n  - 1$:
    \begin{center}
    \begin{tabular}{c c c c c c c}
         &       & $A_i$ & & & & \\
     $\nearrow$ & $\nearrow$  & \ldots  & $\nwarrow$     & $\nwarrow$  &
$\nwarrow$     & \ldots \\
    ${A_i}_1^1$ & ${A_i}_1^2$ & \ldots  & ${A_i}_1^{n-1}$ & ${A_i}_1^n$  &
    ${A_i}_1^{n+1}$ & \ldots \\
         & $\uparrow$   & \ldots  & $\uparrow$      & $\uparrow$ &
$\uparrow$ & \ldots \\
         &  ${A_i}_2^2$ & \ldots  & ${A_i}_2^{n-1}$ &  ${A_i}_2^n$ &
         ${A_i}_2^{n+1}$ & \ldots  \\
         &       & \ldots   & \ldots       &  \ldots & \ldots       & 
\ldots\\
         &       &     &  $\uparrow$     & $\uparrow$   & $\uparrow$  &
\ldots \\
         &       &     & ${A_i}_{n-1}^{n-1}$ &  ${A_i}_{n-1}^n$  &
         ${A_i}_{n-1}^{n+1}$ & \ldots  \\
         &       &     &           & $\uparrow$  & $\uparrow$ & \ldots  \\
         &       &     &           &  ${A_i}_n^n$  &  ${A_i}_n^{n+1}$
         & \ldots  \\
         &       &     &           &  & $\uparrow$ & \ldots  \\
         &       &     &           &  &  ${A_i}_{n+1}^{n+1}$
         & \ldots \\
    \end{tabular}
  \end{center}
\item the edges between each of the $A_i$ and an argument which does not
  belong to $\cbo$ are kept.
\end{enumerate}
\end{defin}

\paragraph{Example~\ref{ex2bis} -- Unattacked cycle (continuation)} {\it
The graph $\gbo$ containing the unattacked cycle
$A-B-A$ and the argument $C$, which is attacked by $A$, is rewritten as
follows:
    \begin{center}
    \begin{tabular}{c c c}
      \begin{minipage}{5cm}{
    \begin{tabular}{c c c c}
      \multicolumn{4}{c}{$C$}\\
      \multicolumn{4}{c}{$\uparrow$}\\
      \multicolumn{4}{c}{$A$}\\
      $\nearrow$ & $\nearrow$ & $\nwarrow$ & \ldots \\
      ${A}_1^1$ & ${A}_1^2$ & ${A}_1^3$ & \ldots \\
       & $\uparrow$ & $\uparrow$ & \ldots \\
       & ${A}_2^2$ & ${A}_2^3$ & \ldots \\
       &  & $\uparrow$ & \ldots \\
       &  & ${A}_3^3$ & \ldots \\
    \end{tabular}
  }\end{minipage} &
      \begin{minipage}{5cm}{
    \begin{tabular}{c c c c}
      \multicolumn{4}{c}{$B$}\\
      $\nearrow$ & $\nearrow$ & $\nwarrow$ & \ldots \\
      ${B}_1^1$ & ${B}_1^2$ & ${B}_1^3$ & \ldots \\
       & $\uparrow$ & $\uparrow$ & \ldots \\
       & ${B}_2^2$ & ${B}_2^3$ & \ldots \\
       &  & $\uparrow$ & \ldots \\
       &  & ${B}_3^3$ & \ldots \\
    \end{tabular}
  }\end{minipage}
\end{tabular}
\end{center}

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


\begin{defin}[Rewriting of an attacked cycle]\label{rewrite-attack-cyc}
  Let $\cbo= 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
  $\gbo$ which contains $\cbo$ is rewritten as follows:
  \begin{enumerate}
  \item the cycle $\cbo$ is removed,
  \item and replaced by the infinite acyclic graphs, one for each $A_i$
$i= 0 \ldots n
    - 1$:
    \begin{center}
    \begin{tabular}{c c c c c c c}
       &  & $A_i$ & & & & \\
     $\nearrow$ &  $\nearrow$  & \ldots  & $\nwarrow$     & $\nwarrow$  &
$\nwarrow$     & \ldots \\
    $B_i$ & ${A_i}_1^1$ & \ldots  & ${A_i}_1^{n-1}$ & ${A_i}_1^n$  &
    ${A_i}_1^{n+1}$ & \ldots \\
      &  $\uparrow$    & \ldots  & $\uparrow$      & $\uparrow$ &
$\uparrow$ & \ldots \\
      & $B_{(i-1+n) \mbox{\scriptsize{ mod }}n}$  & \ldots  &
${A_i}_2^{n-1}$ &  ${A_i}_2^n$ &
         ${A_i}_2^{n+1}$ & \ldots  \\
      &   & \ldots   & \ldots       &  \ldots & \ldots       &  \ldots\\
      &   &      &  $\uparrow$     & $\uparrow$   & $\uparrow$  & \ldots \\
      &   &      & ${A_i}_{n-1}^{n-1}$ &  ${A_i}_{n-1}^n$  &
         ${A_i}_{n-1}^{n+1}$ & \ldots  \\
      &   &      &  $\uparrow$     & $\uparrow$  & $\uparrow$ & \ldots  \\
      &   &      &  $B_{(i+1) \mbox{\scriptsize{ mod }}n}$   & 
${A_i}_n^n$  &  ${A_i}_n^{n+1}$
         & \ldots  \\
      &   &      &           &  $\uparrow$ & $\uparrow$ & \ldots  \\
      &   &      &           &  $B_i$ &  ${A_i}_{n+1}^{n+1}$
         & \ldots \\
      &   &      &           &  & $\uparrow$ & \ldots  \\
      &   &      &           &   & $B_{(i-1+n) \mbox{\scriptsize{ mod }}n}$
         & \ldots \\
    \end{tabular}
  \end{center}
(the branches leading to $B_k$ exist iff $B_k$ exists\footnote{The
  operator mod is the modulo function.}).
\item the edges between each of the $A_i$ and an argument which does
  not belong to $\cbo$ are kept.
\item the edges between each of the $B_i$ and an argument which does
  not belong to $\cbo$ are kept.
\end{enumerate}
\end{defin}

\paragraph{Example~\ref{ex2-nelle} -- Attacked cycle (continuation)} {\it
The graph $\gbo$ 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:
    \begin{center}
    \begin{tabular}{c c c}
      \begin{minipage}{5cm}{
    \begin{tabular}{c c c c}
      \multicolumn{4}{c}{$C$}\\
      \multicolumn{4}{c}{$\uparrow$}\\
      \multicolumn{4}{c}{$A$}\\
      $\nearrow$ & $\uparrow$  & $\nwarrow$ & \ldots \\
      $D$ & ${A}_1^2$ & ${A}_1^4$ & \ldots \\
          & $\uparrow$ & $\uparrow$ & \ldots \\
          & ${A}_2^2$ & ${A}_2^4$ & \ldots \\
          & $\uparrow$ & $\uparrow$ & \ldots \\
          & $D$ & ${A}_3^4$ & \ldots \\
          & & $\uparrow$ & \ldots \\
          & & ${A}_4^4$ & \ldots \\
          & & $\uparrow$ & \ldots \\
          & & $D$ & \ldots \\
    \end{tabular}
  }\end{minipage} &
      \begin{minipage}{5cm}{
    \begin{tabular}{c c c c}
      \multicolumn{4}{c}{$E$}\\
      \multicolumn{4}{c}{$\uparrow$}\\
      \multicolumn{4}{c}{$B$}\\
      $\nearrow$ & $\uparrow$ & $\nwarrow$ & \ldots \\
      ${B}_1^1$ & ${B}_1^3$ & ${B}_1^5$ & \ldots \\
      $\uparrow$ & $\uparrow$ & $\uparrow$ & \ldots \\
      $D$ & ${B}_2^3$ & ${B}_2^5$ & \ldots \\
          & $\uparrow$ & $\uparrow$ & \ldots \\
          & ${B}_3^3$ & ${B}_3^5$ & \ldots \\
          & $\uparrow$ & $\uparrow$ & \ldots \\
          & $D$ & ${B}_4^5$ & \ldots \\
          & & $\uparrow$ & \ldots \\
          &  & ${B}_5^5$ & \ldots \\
          & & $\uparrow$ & \ldots \\
          & & $D$ & \ldots \\
    \end{tabular}
  }\end{minipage}
\end{tabular}
\end{center}

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

\paragraph{Note:} If there exist several cycles in a graph, we have two
cases.
\begin{itemize}
\item 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.
\item 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~\ref{algo-calcul-val-tuple}).
\end{itemize}


%*****************************************************************************
%*****************************************************************************
\subsubsection{A gradual valuation with tuples for general graphs}
\label{nelle-eval-tuple}
%*****************************************************************************
%*****************************************************************************

Using the definitions given in Sections~\ref{val-tuple-acyclic}
and~\ref{study-cycle}, the gradual valuation with tuples given by
Definition~\ref{def-nelle-eval-tuple} is applicable for arbitrary
graphs {\em after the rewriting process}.

Let us apply the rewriting process and
Definition~\ref{def-nelle-eval-tuple} on different examples.


%*****************************************************************************
%\paragraph{Unattacked cycle which attacks some arguments}
%*****************************************************************************
\paragraph{Example~\ref{ex2bis} -- Unattacked cycle (continuation)}{\it
\ \\
Consider the following graph:

\centerline{\includegraphics[scale=0.7]{cas10bis.eps}}

The rewriting of this graph has been given in Section~\ref{study-cycle}.\\

Definition~\ref{def-nelle-eval-tuple} produces:
 \begin{quote}

$v_p(A) = (v_i(A_1^1) \oplus 1) \star \ldots  \star (v_i(A_1^n) \oplus 1)
\star \ldots $ \\

$v_i(A) = (v_p(A_1^1) \oplus 1) \star \ldots  \star (v_p(A_1^n) \oplus 1)
\star \ldots $

 \end{quote}

Applying Definition~\ref{def-nelle-eval-tuple} for different arguments in
the rewritten graph produces the following equalities:
\begin{itemize}
\item $v(A_n^n) = [0^{\infty},()]$ for each $n \geq 1$
\item $v(A_{n-1}^n) = [(),(1)]$ for each $n \geq 2$
\item $v(A_n^m) = [v_p(A_{n+2}^m) \oplus 2, v_i(A_{n+2}^m) \oplus 2]$ for
each n $\geq 1$ and $m \geq {n+2}$
\end{itemize}

So, using the above equalities in the formulae giving $v_p(A)$ and
$v_i(A)$, we define two sequences of tuples : a sequence ($x_k$, $k \geq
1$) of infinite tuples of even integers, and a sequence ($y_k$, $k \geq
1$) of infinite tuples of odd integers

 \begin{quote}

 $x_k = (2) \star (v_i(A_{2k-1}^{2k+1}) \oplus 1) \star \ldots  \star
(v_i(A_{2k-1}^n) \oplus 1) \star \ldots $ \\

 $y_k = (1) \star (v_p(A_{2k-1}^{2k+1}) \oplus 1) \star \ldots  \star
(v_p(A_{2k-1}^n) \oplus 1) \star \ldots $

 \end{quote}

From the results stated in Property~\ref{comm-assoc}, it is easy to prove
that $v_p(A) = x_1$ and for each $k \geq 1$, $x_k = (2) \star (x_{k+1}
\oplus 2) $. \\

Similarly, $v_i(A) = y_1$ and for each $k \geq 1$, $y_k = (1) \star
(y_{k+1} \oplus 2) $. \\

These equations enable to prove that :
\begin{quote}

  For each even integer $p$ $p > 0$, $p$ belongs to each tuple $x_i, i
\geq 1$.

  For each odd integer $p$, $p$ belongs to each tuple $y_i$, $i \geq 1$.

\end{quote}

The proof is done by induction on p.\\

So, $v(A) = v(B) = [(2,4,6,\ldots), (1,3,5,\ldots)]$.

Then, $v(C) =
[(2,4,6,\ldots), (3,5,7,\ldots)]$.
} \\

Note that all the above results can be readily extended to an unattacked
cycle of length n, $n \geq 2$.

\begin{propriet}[Properties of unattacked
cycles]\label{value-unattacked-cycle}\ \\
  For each unattacked cycle, for each argument $A$ of the cycle, $v(A) =
[(2,4,6,\ldots), (1,3,5,\ldots)]$.
\end{propriet}


%*****************************************************************************
%\paragraph{Attacked cycle}
%*****************************************************************************

\paragraph{Example~\ref{ex2-nelle} -- Attacked cycle (continuation)}{\it
Consider the following graph:

\centerline{\includegraphics[scale=0.7]{ex-circuit2.eps}}

The rewriting of this graph has been given in Section~\ref{study-cycle}.\\

Definition~\ref{def-nelle-eval-tuple} produces:
 \begin{quote}

$v_p(A) = (v_i(D) \oplus 1) \star (v_i(A_1^2) \oplus 1) \star \ldots 
\star (v_i(A_1^{2n}) \oplus 1) \star \ldots $ \\

$v_i(A) = (v_p(D) \oplus 1) \star(v_p(A_1^2) \oplus 1) \star \ldots  \star
(v_p(A_1^{2n}) \oplus 1) \star \ldots $

and also

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

$v(A_n^n) = [(),(1)]$ for each $n \geq 2$

 \end{quote}

As done in the treatment of Example~\ref{ex2bis}, the formulae giving
$v_p(A)$ and $v_i(A)$ can be rewritten in order to bring to light some
interesting sequences of tuples.

\begin{quote}

 $x'_k =  (v_i(A_{2k-1}^{2k}) \oplus 1) \star \ldots  \star
(v_i(A_{2k-1}^{2(k+p)}) \oplus 1) \star \ldots $ \\

 $y'_k = (1) \star (v_p(A_{2k-1}^{2k}) \oplus 1) \star \ldots  \star
(v_p(A_{2k-1}^{2(k+p)}) \oplus 1) \star \ldots $

 \end{quote}

Then, it is easy to prove that $v_p(A) = x'_1$ and for each $k \geq 1$,
$x'_k = (x'_{k+1} \oplus 2) $. \\

Similarly, $v_i(A) = y'_1$ and for each $k \geq 1$, $y'_k = (1) \star
(y'_{k+1} \oplus 2) $. \\

The first equation enables to prove that $x'_1$ is the empty
tuple\footnote{The proof is the following:.
\begin{monitem}
\item $x'_1$ contains only even integers.
\item For each k, $x'_k \neq 0^{\infty}$ since $x'_k$ is the result of the
addition of a tuple and an integer.
\item If $x'_1$ is not empty, let $e_1$ denote the least even integer
present in $x'_1$. As $x'_1 = x'_2 \oplus 2$, $x'_2$ is not empty and
$e_2$ will denote the least integer present in $x'_2$. We have $e_1 = e_2
+ 2$. So, we are able to build a sequence of positive even integers $e_1,
e_2, \ldots$, which is strictly decreasing. That is impossible. So, $x'_1
= ()$.
\end{monitem}}. \\

The second equation has already been solved and produces $y'_1 =
(1,3,5,\ldots)$. \\

So, $v(A) = [(), (1,3,5,\ldots)]$. For $B$, we can reason as for $A$,
and we have $v(B) = [(2,4,6,\ldots),()]$. Then, $v(C) =
[(2,4,6,\ldots),()]$, $v(E) = [(),(3,5,7\ldots)]$.


\paragraph{Notation:} in order to simplify the writing, we will not
repeat the values inside the tuples (we will just indicate under each
value how many times it appears). For example:

$$[(2,4,4,6,6,6,8,8,8,8\ldots),(3,5,5,7,7,7,9,9,9,9\ldots)]$$
will be denoted by
$$[(2,\underbrace{4}_{2},\underbrace{6}_{3},\underbrace{8}_{4},\ldots),(3,\underbrace{5}_{2},\underbrace{7}_{3},\underbrace{9}_{4},\ldots)]$$
}


%*****************************************************************************
\paragraph{Conclusion about cycles}\label{concl-nelle-eval}
%*****************************************************************************

Cycles are expensive since all the values obtained are infinite.

In appendix~\ref{algo-calcul-val-tuple}, we introduce an algorithm for
computing these tupled values. It uses a process of value propagation
and is parameterised by a maximum ``number of runs through a cycle''.
This number will be used in order to stop the propagation mechanism
and to obtain finite (thus incomplete) tupled values.




%*****************************************************************************
%*****************************************************************************
\subsubsection{Comparison of tupled values}
\label{compar-val-tuple}
%*****************************************************************************
%*****************************************************************************

In this section, we define the comparison relation between arguments
(so, between some particular tupled values), using the following idea:
an argument $A$ is better than an argument $B$ iff $A$ has a better
defence (for it) and a lower attack (against it).

The first idea is to use a lexicographic ordering on the tuples.  This
lexicographic ordering denoted by $\leq_{lex\infty}$ on $\tbo$ is
defined by:

\begin{defin}[Lexicographic ordering  on
  tuples]\label{def-ordre-lex-infini}\ \\
  Let $(x_1,\ldots, x_n, \ldots)$ and $(y_1,\ldots, y_m, \ldots)$ be 2  finite
  or infinite tuples $\in \tbo$.
  
  $(x_1,\ldots, x_n, \ldots) <_{lex\infty} (y_1,\ldots, y_m, \ldots)$ iff $\exists i \geq 1$ such
  that:
  \begin{monitem}
  \item  $\forall j<i$, $x_j = y_j$ and 
  \item $y_i$ exists and:
    \begin{monitem}
     \item either the tuple $(x_1,\ldots, x_n, \ldots)$ is finite with a
       number of elements equal to $i-1$ (so, $x_i$ does not exist), 
    \item or $x_i$ exists and $x_i < y_i$.
  \end{monitem}
\end{monitem}  

  $(x_1,\ldots, x_n, \ldots) =_{lex\infty} (y_1,\ldots, y_m, \ldots)$ iff
 the tuples contain the same number $p \in \Nat \cup \{\infty\}$ of elements and $\forall i$,
  $1 \leq i \leq p$, $x_i = y_i$.
  
  So, we define: $(x_1,\ldots, x_n, \ldots) \leq_{lex\infty} (y_1,\ldots, y_m, \ldots)$ iff

\centerline{$(x_1,\ldots, x_n, \ldots)
  =_{lex\infty} (y_1,\ldots, y_m, \ldots)$ or $(x_1,\ldots, x_n, \ldots) <_{lex\infty} (y_1,\ldots, y_m,
  \ldots)$.}
\end{defin}

The ordering $<_{lex\infty}$ is a generalisation of the classical
lexicographic ordering (see~\citeR{Xuong92}) to the case of infinite
tuples. This ordering is complete but not well-founded (there exist
infinite sequences which are strictly non-increasing: $(0)$
$<_{lex\infty}$ $(0,0)$ $<_{lex\infty}$ \ldots $<_{lex\infty}$ $(0,
\ldots, 0, \ldots)$ $<_{lex\infty}$ \ldots $<_{lex\infty}$ $(0, 1)$).


Since the even values and the odd values in the tupled value of an
argument do not play the same role, we cannot use a classical
lexicographic comparison. So, we compare tupled values in two steps:
\begin{monitem}
\item The ``first step'' \emph{compares the number of attack branches
    and the number of defence branches} of each argument. So, we have
  two criteria (one for the defence and the other for the attack).
  These criteria are aggregated using a {\em cautious method}: we
  conclude if one of the arguments has more defence branches (it is
  better according to the defence criterion) and less attack branches
  than the other argument (it is also better according to the attack
  criterion). Note that we conclude positively only when {\em all} the
  criteria agree: if one of the arguments has more defence branches
  (it is better according to the defence criterion) and more attack
  branches than the other argument (it is worse according to the
  attack criterion), the arguments are considered to be incomparable.
\item Else, the arguments have the same number of defence branches and
  the same number of attack branches, and a ``second step''
  \emph{compares the quality of the attacks and the quality of the
    defences} using the length of each branch. This comparison is made
  with a lexicographic principle (see
  Definition~\ref{def-ordre-lex-infini}) and gives two criteria which
  are again aggregated using a cautious method. In case of
  disagreement, the arguments are considered to be incomparable.
\end{monitem}

Let us consider some examples:
\begin{monitem}
\item $[(2),(1)]$ is better than $[(2),(1,1)]$ because there are less
  attack branches in the first tupled value than in the second tupled
  value, the numbers of defence branches being the same (first step).
\item $[(2),(1)]$ is incomparable with $[(2,2),(1,1)]$ because there are
  less defence branches and less attack
  branches in the first tupled value than in the second tupled value (first step). 
\item $[(2),(3)]$ is better than $[(2),(1)]$ because there are weaker
  attack branches in the 
  first tupled value than in the second tupled
  value (the attack branch of the first tupled value is longer than
  the one of the second tupled value), the defence branches being
  the same (second step, using the lexicographic comparison applied on
  even parts then on odd parts of the tupled values).
\item $[(2),(3)]$ is better than $[(4),(3)]$ because there are stronger
  defence branches in the 
  first tupled value than in the second tupled
  value (the defence branch is shorter in the first tupled value than
  in the  second tupled value), the attack branches being
  the same (second step).
\item $[(2),(1)]$ is incomparable with $[(4),(3)]$ because there are worse attack
  branches and better defence branches  in
  the first tupled value than in the second tupled value
  (second step). 
\end{monitem}

The comparison of arguments is done using
Algorithm~\ref{compar-tuple3} which implements the principle of a
double comparison (first quantitative, then qualitative) with two
criteria (one defence criterion and one attack criterion) using a
cautious method.

\begin{algorithm}[H]
\small
\dontprintsemicolon
\SetVline
 \% {\bf Description of the parameters:} \hfill \% \;
 \%  $v$, $w$: 2  tupled values \hfill \% \;
 \%  {\bf Notations:} \hfill \% \;
 \% \tab $|v_p|$ (resp. $|w_p|$): number of elements in the even component of  $v$ (resp. $w$) \hfill \% \;
 \% \tab\tab if $v_p$ (resp. $w_p$) is infinite then $|v_p|$
 (resp. $|w_p|$) is taken equal to
  $\infty$ \hfill \% \;
 \% \tab$|v_i|$ (resp. $|w_i|$): number of elements in the odd component
 of  $v$ (resp. $w$) \hfill \% \;
 \% \tab\tab if $v_i$ (resp. $w_i$) is infinite then  $|v_i|$ (resp. $|w_i|$) is taken equal to
  $\infty$ \hfill \% \;
 \% \tab As usual, $\succ$ will denote the strict relation
associated with $\succeq$ defined by:  \hfill \% \;
 \% \tab \tab $v \succ w$ iff $v \succeq w$ and
not($w \succeq v$).\hfill \% \;
\Indm \BlankLine
\Begin {\nl
\lIf {$v = w$}
{$v \succeq  w$ AND $w \succeq v$\hfill \% Case 1 \%\;
}
\nl\Else
{\nl\If {$|v_i| = |w_i|$ AND $|v_p| = |w_p|$}
  { \hfill \%  lexicographic comparisons  between $v_p$ and
                     $w_p$ and between $v_i$ and $w_i$ \% \;  
    \nl\lIf {$v_p \leq_{lex\infty} w_p$ AND $v_i
      \geq_{lex\infty} w_i$}
    {$v \succ  w$ \hfill \% case 2 \% \;
      }
    \nl\Else
    {\nl\lIf {$v_p \geq_{lex\infty} w_p$ AND $v_i
        \leq_{lex\infty} w_i$} 
      {$v \prec  w$\hfill \% case 3 \%\;
        }
      \nl\lElse {
        $v \not\succeq w$ AND $v \not\preceq  w$ \hfill \%
        Incomparable tupled values.  case 4 \%  \;
        }
      }
    }
  \nl\Else  
  {\nl\lIf {$|v_i| \geq |w_i|$ AND $|v_p| \leq |w_p|$}
    {$v \prec  w$ \hfill \% case 5 \%\;
      }
    \nl\Else
    {\nl\lIf {$|v_i| \leq |w_i|$ AND $|v_p| \geq |w_p|$}
      {$v \succ  w$ \hfill \% case 6 \%\;
        }
      \nl\lElse {
        $v \not\succeq w$ AND $v \not\preceq  w$ \hfill \%
        Incomparable tupled values. Case 7 \% \;
        }
      }
    }
  }
}
\caption{Comparison of two tupled values\label{compar-tuple3}}
\end{algorithm}

Algorithm~\ref{compar-tuple3} defines a partial preordering on the
set $v(\abo)$:

\begin{propriet}[Partial preordering]\label{prop-preordre}\label{tuple3-ordre}\label{valmaxminpreordre}
  Algorithm~\ref{compar-tuple3} defines a partial preordering
  $\succeq$ on the set $v(\abo)$.
  
  The tupled value $[0^{\infty},()]$ is the only maximal value of the
  partial preordering $\succeq$.
  
  The tupled value $[(),1^{\infty}]$ is the only minimal value of the
  partial preordering $\succeq$.
\end{propriet}


\paragraph{Notation:} the partial preordering $\succeq$ on the set $v(\abo)$
induces a partial preordering on the arguments (the partial
preordering on $\abo$ will be denoted like the partial preordering on
$v(\abo)$): $A \succeq B$ if and only if $v(A) \succeq
v(B)$\footnote{We will also use the notation $B \preceq A$ defined by:
  $B \preceq A$ iff $A \succeq B$.}.

In order to present the underlying principles satisfied by the global
valuation, we first consider the different ways for modifying the
defence part or the attack part of an argument:

\begin{defin}[Adding/removing a branch to an
  argument]\label{def-add-rem-branch}\ \\
  Let $A$ be an argument whose tupled value is $v(A) = [v_p(A),
  v_i(A)]$ with $v_p(A) = (x^p_1, \ldots, x^p_n)$ and $v_i(A) =
  (x^i_1, \ldots, x^i_m)$ ($v_p(A)$ or $v_i(A)$ may be empty but not
  simultaneously). 

Adding (resp. removing) a defence branch to $A$
  is defined by: 

$v_p(A)$ becomes $\sort(x^p_1, \ldots, x^p_n,x^p_{n+1})$ where $x^p_{n+1}$
is the length of the added branch (resp. 
    $\exists j \in [1..n]$ such that $v_p(A)$ becomes $(x^p_1, \ldots,
    x^p_{j-1}, x^p_{j+1}, \ldots, x^p_n)$).

And the same thing on $v_i(A)$ for adding (resp. removing) an attack branch to $A$.
\end{defin}


\begin{defin}[Increasing/decreasing the length of a branch of an
  argument]\label{def-inc-dec-lg-branch}\ \\
  Let $A$ be an argument whose tupled value is $v(A) = [v_p(A),
  v_i(A)]$ with $v_p(A) = (x^p_1, \ldots, x^p_n)$ and $v_i(A) =
  (x^i_1, \ldots, x^i_m)$ ($v_p(A)$ or $v_i(A)$ may be empty but not
  simultaneously). 

Increasing (resp. decreasing) the length of a defence branch of $A$ is
  defined by:
    
    $\exists j \in [1..n]$ such that $v_p(A)$ becomes $(x^p_1, \ldots,
    x^p_{j-1}, x'^p_j, x^p_{j+1}, \ldots, x^p_n)$ where $x'^p_j >
    x^p_j$ (resp. $x'^p_j <  x^p_j$) and the parity of $x'^p_j$ is the parity of $x^p_j$.

And the same thing on $v_i(A)$ for increasing (resp. decreasing) an attack branch to $A$.
\end{defin}


\begin{defin}[Improvement/degradation of the
  defences/attacks]\label{def3-ame-det-def-att}\ \\
  Let $A$ be an argument whose tupled value is $v(A) = [v_p(A),
  v_i(A)]$ ($v_p(A)$ or $v_i(A)$ may be empty but not
  simultaneously). We define:
\begin{quote}
\begin{description}
\item[An improvement (resp. degradation) of the defence] consists in
  \begin{monitem}
  \item adding a defence branch to $A$ if initially
    $v_p(A) \neq 0^{\infty}$ (resp. removing a defence branch of $A$);
  \item or decreasing (resp. increasing) the length of a defence branch of $A$;
  \item or removing the only defence branch leading to $A$
    (resp. adding a defence branch leading to $A$ if initially 
      $v_p(A)= 0^{\infty}$);
  \end{monitem}

\item[An improvement (resp. degradation) of the attack] consists in
  \begin{monitem}
  \item adding (resp. removing) an attack branch to $A$;
  \item or decreasing (resp. increasing) the length of an attack branch of $A$.
  \end{monitem}
\end{description}
\end{quote}
\end{defin}


\begin{propriet}[Underlying principles]\label{prop-principe-tuple}
  Let $v$ be a valuation with tuples
  (Definition~\ref{def-nelle-eval-tuple}) associated with 
  Algorithm~\ref{compar-tuple3}, $v$ respects the following
  principles:
\begin{description}
\item[{\bf P1$'$}] The valuation is maximal for an argument without
  attackers and non maximal for an argument which is attacked (whether
  it is defended or not).  
\item[{\bf P2$'$}] The valuation of an argument takes into account all
the branches which are rooted in this argument.
\item[{\bf P3$'$}] The improvement of the defence or the degradation
  of the attack of an argument leads to an increase of the value of
  this argument. 
\item[{\bf P4$'$}] The improvement of the attack or the degradation of the
defence of an argument leads to a decrease of the value of the
argument.  
\end{description}
\end{propriet}

\paragraph{Example~\ref{ex} (continuation)} {\it With the valuation
  with tuples, we obtain:

\begin{monitem}
\item $v(E_1) = v(D_2) = v(D_3) = v(C_4) = v(B_4) = [0^\infty,()]$,
\item $v(D_1) = v(C_2) = v(C_3) = v(B_3) = [(),(1)]$,
\item $v(C_1) = v(B_2) = [(2),()]$,
\item $v(B_1) = [(2),(3)]$,
\item $v(A) = [(2,4),(1,3,3)]$.
\end{monitem}

So, we have:

  \begin{center}
  \begin{tabular}{c c c}
$E_1, D_2, D_3, C_4, B_4$ & & \\
$\succ $ & & \\
$C_1, B_2$ & & $E_1, D_2, D_3, C_4, B_4$ \\
$\succ $ & but also & $\succ $\\
$B_1$ & & $A$\\
$\succ $ & & \\
$D_1, C_2, C_3, B_3$ & & \\
\end{tabular}
\end{center}

$A$ is incomparable with almost all the other arguments (except with
the leaves of the graph).

Similarly, on the hatched part of the graph, we obtain the
following results:

$$E_1, D_2 \succ C_1 \succ B_1 \succ A \succ D_1, C_2$$

$A$ is now comparable with all the other arguments (in
particular, $A$ is ``worse'' than its defender $C_1$ and than its
direct attacker $B_1$).
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%  Main differences between ``local'' and ``global'' valuations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Main differences between ``local'' and ``global'' valuations}
\label{loc-glo}


\citeA{CLS03c} give a comparison of these approaches with some
existing approaches (\citeR{Dung95,JV99,BH01}), and also a comparison
of the ``local'' approaches and the ``global'' approach.  The
improvement of the global approach proposed in this paper does not
modify the main results of this comparison.

Let us recall here an example of the essential point which
differentiates them (this example has already been presented at the
beginning of Section~\ref{eval-grad}):

\centerline{\includegraphics[scale=0.75]{compar-loc-glo.eps}}

In the local approach, $B'$ is better than $B$ (since $B'$ suffers one
attack whereas $B$ suffers two attacks).

In the global approach, $B$ is better than $B'$ (since it has at least
a defence whereas $B'$ has none). In this case, $C_1$ loses its
negative status of attacker, since it is in fact ``carrying a
defence'' for $B$.

The following table synthesises the results about the different proposed valuations:

{\small
\begin{center}
\begin{tabular}{| c | c | c | c | c | c | c |}
  \multicolumn{7}{c}{\ }\\
  \multicolumn{7}{c}{\bf\it global approach}\\
  \multicolumn{7}{c}{\ }\\
  \begin{minipage}{3cm}
    arguments having only attack branches
  \end{minipage} & $\preceq$ &
  \begin{minipage}{3cm}
     arguments having attack branches and defence branches
  \end{minipage} & $\preceq$ &
  \begin{minipage}{3cm}
   arguments having only defence branches 
  \end{minipage} & $\preceq$ &
  \begin{minipage}{1.5cm}
   arguments never attacked
  \end{minipage}\\
  \multicolumn{7}{c}{\ }\\\hline
\end{tabular}
\end{center}
}
{\small
\begin{center}
\begin{tabular}{| c | c | c | c | c | c | c |}
  \multicolumn{7}{c}{\ }\\
  \multicolumn{7}{c}{\bf\it local approach}\\
  \multicolumn{7}{c}{\ }\\
  \multicolumn{5}{ c }{
    \begin{tabular}{| c | c | c | c | c |}
  \begin{minipage}{3cm}
   arguments having several unattacked direct attackers
  \end{minipage} & $\preceq$ &
  \begin{minipage}{3cm}
   arguments having only one unattacked direct attacker 
  \end{minipage} & $\preceq$ &
  \begin{minipage}{3cm}
   arguments having only one attacked direct attacker (possibly defended)
  \end{minipage}\\\hline
  \multicolumn{5}{| c |}{\begin{minipage}{10cm}
   arguments having several attacked direct attackers (possibly defended)
  \end{minipage}}
\end{tabular}} & $\preceq$ &
  \begin{minipage}{1.5cm}
    arguments never attacked 
  \end{minipage}\\
  \multicolumn{7}{c}{\ }
\end{tabular}
\end{center}
}

The difference between the local approaches and the global approach is
also illustrated by the following property:


\begin{propriet}[Independence of branches in the global approach]\label{prop-ind-branches}
\ \\
Let  $A$ be an argument having the following direct attackers:
\begin{monitem}
\item  $A_1$ whose value is $v(A_1) = [(a^1_{p_1}, \ldots, a^1_{p_{m_1}}),(a^1_{i_1},
  \ldots, a^1_{i_{m_1}})]$,
\item \ldots, 
\item $A_n$ whose value is $v(A_n) = [(a^n_{p_1}, \ldots,
  a^n_{p_{m_n}}),(a^n_{i_1}, \ldots, a^n_{i_{m_n}})]$.
\end{monitem}
Let $A'$ be an argument having the following direct attackers:
\begin{monitem}
\item  $A^1_{p_1}$ whose value is
$v(A^1_{p_1}) = [(a^1_{p_1})()]$, 
\item  \ldots, 
\item  $A^1_{p_{m_1}}$ whose value is
$v(A^1_{p_{m_1}}) = [(a^1_{p_{m_1}})()]$, 
\item  $A^1_{i_1}$ whose value is
$v(A^1_{i_1}) = [()(a^1_{i_1})]$, 
\item  \ldots, 
\item  $A^1_{i_{m_1}}$ whose value is
$v(A^1_{i_{m_1}}) = [()(a^1_{i_{m_1}})]$, 
\item  \ldots, 
\item  $A^n_{p_1}$ whose value is
$v(A^n_{p_1}) = [(a^n_{p_1})()]$, 
\item  \ldots,  
\item  $A^n_{p_{m_n}}$ whose value is
$v(A^n_{p_{m_n}}) = [(a^n_{p_{m_n}})()]$, 
\item $A^n_{i_1}$ whose value is
$v(A^n_{i_1}) = [()(a^n_{i_1})]$, 
\item \ldots,  
\item $A^n_{i_{m_n}}$ whose value is
$v(A^n_{i_{m_n}}) = [()(a^n_{i_{m_n}})]$.
\end{monitem}
Then $v(A) = v(A')$.
\end{propriet}



This property illustrates the ``independence'' of branches during the
computation of the values in the global approach, even when these
branches are not graphically independent. On the following example,
$A$ and $A'$ have the same value $[(2,2)()]$ though they are the root
of different subgraphs:

\centerline{\includegraphics[scale=0.7]{independance.eps}}
    
This property is not satisfied by the local approach since, using the
underlying principles of the local approach (see
Property~\ref{prop-principes-eval-loc}), the value of the argument $A$
must be at least as good as (and sometimes better than\footnote{With
  the valuation proposed by~\citeA{BH01}, we obtain: $v(A) =
  \frac{3}{4}$ and $v(A') = \frac{1}{2}$.}) the value of the argument
$A'$ ($A$ having one direct attacker, and $A'$ having two direct
attackers).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%  Conclusion about valuation step
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Conclusion about valuation step}
\label{concl-val}

We have proposed two different gradual valuation models and we are now
able to make a distinction between different arguments using the
preordering associated with a valuation model.  These valuations will
be used for the selection of the arguments (see
Section~\ref{acceptabilite}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  Graduality and acceptability
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Graduality and acceptability} 
\label{acceptabilite}

%In Section~\ref{eval-grad}, we have introduced graduality in the
%interaction-based valuation step.
%After the introduction of graduality in the valuation step (see
%Section~\ref{eval-grad}),  we reiterate this process in this new
%section in order to select the acceptable arguments.

In this section, we now shift to the selection step and introduce
graduality in the notion of acceptability\footnote{This work has been
  presented in a workshop (\citeR{CLS03b}).}.

The basic idea is to select an argument depending on the non-selection
of its direct attackers. Following this idea, we propose two different
methods:
\begin{monitem}
\item The first method consists in refining the classical partition
  issued from Dung's collective acceptability; this refinement may be
  achieved using the gradual valuations defined in
  Section~\ref{eval-grad}.
\item The second method takes place in an individual acceptability and
  consists in defining a new acceptability using only the gradual
  valuations defined in Section~\ref{eval-grad}.
\end{monitem}

%Some of these refinements will use
%the gradual valuations defined in
%Section~\ref{eval-grad}.


%%%%%%%%%%%
%%% Collective acceptability  of~\citeA{Dung95}
%%%%%%%%%%
\subsection{\citeS{Dung95} collective acceptability} 
\label{accep-dung}


In the framework of collective acceptability, we have to consider the
acceptability of a set of arguments.  This acceptability is defined
with respect to some properties and the sets which satisfy these
properties are called {\em acceptable sets} or {\em extensions}. An
argument will be said acceptable if and only if it belongs to an
extension.

\begin{defin}[Basic properties of extensions following~\citeR{Dung95}]
\ \\
Let $\AR$ be an argumentation system, we have:

\begin{description}
\item[Conflict-free set] A set $E \subseteq \abo$ is
  \emph{conflict-free} if and only if $\not \exists A, B \in E$ such
  that $A \rbo B$.
  
\item[Collective defence] Consider $E \subseteq \abo$, $A \in \abo$.
  \emph{$E$ collectively defends $A$} if and only if $\forall B \in
  \abo$, if $B \rbo A, \exists C \in E$ such that $C \rbo B$.
  \emph{$E$ defends all its elements} if and only if $\forall A \in
  E$, $E$ collectively defends $A$.
\end{description}
\end{defin}

\citeA{Dung95} defines several semantics for collective acceptability:
mainly, the \emph{admissible semantics}, the \emph{preferred
  semantics} and the {\em stable semantics} (with corresponding
extensions: the admissible sets, the preferred extensions and the
stable extensions).


\begin{defin}[Some semantics and extensions following~\citeR{Dung95}]\label{def-adm}\label{def-ext-pref}\label{def-ext-stable}
  Let $\AR$ be an argumentation system.

\begin{description}
\item[Admissible semantics (admissible set)]A set $E \subseteq \abo$ is \emph{admissible} if
  and only if $E$ is conflict-free and $E$ defends all its elements.
  
\item[Preferred semantics (preferred extension)]A set $E \subseteq \abo$ is a
  \emph{preferred extension} if and only if $E$ is maximal for set
  inclusion among the admissible sets.
  
\item[Stable semantics (stable extension)] A set $E \subseteq \abo$ is a \emph{stable
    extension} if and only if $E$ is conflict-free and $E$ attacks
  each argument which does not belong to $E$ ($\forall A \in
  \abo\setminus E$, $\exists B \in E$ such that $B \rbo A$).
\end{description}
\end{defin}


Note that in all the above definitions, {\em each attacker} of a given
argument is considered separately (the ``direct attack'' as a whole is
not considered).  \citeA{Dung95} proves that:

\begin{monitem}
\item Any admissible set of $\AR$ is included in a preferred extension
  of $\AR$.
\item There always exists at least one preferred extension of $\AR$.
\item If $\AR$ is well-founded then there is only one preferred
  extension which is also the only stable extension.
\item Any stable  extension is also a preferred extension (the
  converse is false).
\item There is not always a stable extension.
\end{monitem}


\begin{propriet}\label{non-att-ext-pref}\label{non-att-ext-stab}
  The set of leaves ({\it i.e.} $\{A | \rbo{^-}(A) = \varnothing\}$)
  is included in every preferred extension and in every stable
  extension.
\end{propriet}



%*****************************************************************************
%*****************************************************************************
\subsection{Different  levels of collective acceptability}\label{3-niveau}\label{accep1}\label{3niveau-plus-1}
%*****************************************************************************
%*****************************************************************************

%%%%% Primary levels
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsubsection{Primary levels}

Under a given semantics, and following Dung, the acceptability of an
argument depends on its membership to an extension under this
semantics. We consider three possible cases\footnote{The terminology
  used in this section is also used in the domain of nonmonotonic
  reasoning (see~\citeR{PL92}): the word {\em uni} comes from the word
  {\em universal} which is a ``synonym'' of the word {\em
    skeptical}, and the word {\em exi} comes from the word {\em
    existential} which is a ``synonym'' of the word {\em
    credulous}. We have chosen to use the words {\em uni} and {\em
    exi} because they recall the logical quantificators $\forall$
  ({\em for all}) and $\exists$ ({\em exists at least one}).}:

\begin{monitem}
\item the argument can be \emph{uni-accepted}, when it belongs to all
  the extensions of this semantics,
\item or the argument can be \emph{exi-accepted}, when it belongs to
  at least one extension of this semantics,
\item or the argument can be \emph{not-accepted} when it does not
  belong to any extension of this semantics.
\end{monitem}

However, these three levels seem insufficient.  For example, what
should be concluded in the case of two arguments $A$ and $B$ which are
exi-accepted and such that $A \rbo B$ or $B \rbo A$?


%%%%% First  refinement
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsubsection{First  refinement}\label{3niveau-plus-1}
\bigskip

So, we introduce a new definition which takes into account the situation
of the argument w.r.t. its attackers. This refines the class of the
exi-accepted arguments under a given semantics $S$.

\begin{defin}[Cleanly-accepted argument]\label{def1}
  Consider $A \in \abo$, $A$ is {\em cleanly-accepted} if and only if
  $A$ belongs to at least one extension of $S$ and $\forall B \in
  \abo$ such that $B \rbo A$, $B$ does not belong to any extension of
  $S$.
\end{defin}

Thus, we capture the idea that an argument will be better accepted,
%better, in the point of view of the acceptability, 
if its attackers are not-accepted.


\begin{propriet}\label{prop-uni-acc-prop-acc}
%Let $S$ be a semantics in the sense of~\citeA{Dung95}. 
  Consider $A \in \abo$ and a semantics $S$ such that each extension
  for $S$ is conflict-free.
If $A$ is uni-accepted then $A$ is cleanly-accepted. The converse is false.
\end{propriet}

The notion of cleanly-accepted argument refines the class of the
exi-accepted arguments. For a semantics $S$ and an argument $A$, we
have the following states:
\begin{monitem}
\item $A$ can be \emph{uni-accepted}, if $A$ belongs to all the
  extensions for $S$ (so, it will also be cleanly-accepted);
\item or $A$ can be \emph{cleanly-accepted} (so, 
  it is by definition also exi-accepted); note that it is possible that the
  argument is also uni-accepted;
\item or $A$ can be \emph{only-exi-accepted}, if $A$ is not
  cleanly-accepted, but  $A$  is exi-accepted;
\item or $A$ is \emph{not-accepted} if $A$ does not belong to any
  extension for $S$. 
\end{monitem}

\begin{ex}\label{ex3} Consider the following argumentation system.

\begin{tabular}{c c c}
  \begin{minipage}{4cm}
    \centerline{\includegraphics[scale=0.55]{ex-mfi1.eps}}
  \end{minipage} & & 
  \begin{minipage}{10cm}
    There are two preferred extensions $\{D, C_2, A, G\}$ and $\{D, C_2, E,
    G, I\}$. So, for the preferred semantics, the acceptability levels
    are the following:
\begin{monitem}
\item $D$, $C_2$ and $G$ are uni-accepted,
\item $I$ is  cleanly-accepted but not uni-accepted,
\item $A$ and $E$ are only-exi-accepted,
\item $B$, $C_1$, $F$, $H$ and $J$ are not-accepted.
\end{monitem}
\end{minipage}
\end{tabular}
\end{ex}

%%%%% Some particular cases
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsubsection{Some particular cases} 
\bigskip

Note that, in all the cases where there is only one extension, the first three
levels of acceptability coincide\footnote{If there is only one
  extension then the fact that $A$ belongs to all the extensions is
  equivalent to the fact that $A$ belongs to at least one extension.
  Moreover, with only one extension containing $A$, all the attackers
  of $A$ do not belong to an extension. So, $A$ is cleanly-accepted.}.
This is the case:
\begin{monitem}
\item Under the preferred semantics, when there is no even cycle
  (see~\citeR{Doutre02}).
\item Under the basic semantics (another semantics proposed by Dung --
  see~\citeR{Dung95,Doutre02} -- which is not presented here and which
  has only one extension).
\end{monitem}

Looking more closely, we can prove the following result (proof in Appendix~\ref{annexe}):

\begin{propriet}\label{uni-prop-stable}
  Under the stable semantics, the class of the uni-accepted arguments
  coincides with the class of the cleanly-accepted arguments.
\end{propriet}

Then, using a result issued from the work of~\citeA{DBC01a,DBC02} and reused
by~\citeA{Doutre02} which shows that, when there is no odd cycle, all
the preferred extensions are stable\footnote{This corresponds to the
  consistent argumentation system proposed by~\citeA{Dung95}.}, we
apply Property~\ref{uni-prop-stable} and we obtain the following
consequence:

\begin{conseq}\label{uni-prop-pref-ss-circuit}
  Under the preferred semantics, when there is no odd cycle, the class
  of the uni-accepted arguments coincides with the class of the
  cleanly-accepted arguments.
\end{conseq}


%\subsubsection{Comparison based on gradual valuation}\label{accep1}
%*****************************************************************************
%\bigskip

Finally, the exploitation of the gradual interaction-based valuations (see
Section~\ref{eval-grad}) allows us to define new levels of collective
acceptability.

Let $v$ be a gradual valuation and let $\succeq$ be the associated
preordering (partial or complete) on $\abo$. This preordering can be
used inside each acceptability level (for example, the level of the
exi-accepted arguments) in order to identify arguments which are
better accepted than others.

\paragraph{Example~\ref{ex3} (continuation)} {\it Two different 
gradual valuations are applied on the same graph:\\

\centerline{\includegraphics[scale=0.8]{ex-mfi3-angl.eps}}


With the instance of the generic valuation proposed by~\citeA{BH01}
(see Section~\ref{app1}), we obtain the following comparisons:

$$D, C_2 \succ I \succ E \succ G \succ J \succ C_1,F \succ A \succ H \succ B$$


\centerline{\includegraphics[scale=0.8]{ex-mfi2bis-angl.eps} }



With the global valuation with tuples presented in Section~\ref{tuples}, we
obtain the following comparisons:

$$D, C_2 \succ G \succ B \succ F, C_1$$
$$D, C_2 \succ A \succ E$$
$$D, C_2 \succ H \succ E$$
$$D, C_2 \succ I$$
$$D, C_2 \succ J$$
So, all the arguments belonging to a cycle are incomparable with
$G$, $B$, $F$, $C_1$ and, even between them, there are few
comparison results.}\\

If we apply the preordering induced by a valuation without respecting
the acceptability levels defined in this section,
counter-intuitive situations may happen. In Example~\ref{ex3}, we
obtain:

\begin{monitem}
\item With the valuation of~\citeA{BH01} and under the preferred
  semantics, $E \succ G$ despite the fact that $G$ is uni-accepted and
  $E$ is only-exi-accepted.
\item With the valuation with tuples and under the preferred
  semantics, $H \succ E$ despite the fact that $E$ is
  only-exi-accepted and $H$ is not-accepted.
\end{monitem}

These counter-intuitive situations illustrate the difference between
the acceptability definition and the valuation definitions (even if
both use the interaction between arguments, they do not use it in the
same way).


%*****************************************************************************
%*****************************************************************************
%*****************************************************************************
\subsection{Towards a gradual individual acceptability}
\label{accep-eval-grad}\label{accep2}
%*****************************************************************************
%*****************************************************************************
%*****************************************************************************

The individual acceptability is based on the comparison of an argument
with its attackers.

The first proposal has been to select an argument if and only if it
does not have any attacker (see~\citeR{EFK93}).

This has later been extended by~\citeA{AC98} where, using a preference
relation between arguments (an intrinsic valuation), an argument is
accepted if and only if it is preferred to each of its attackers.

Following this proposal, we propose the same mechanism but with the
{\em interaction-based valuation}.

%\subsubsection{Situation of an argument w.r.t. its attackers}\label{accep2}
%*****************************************************************************

Given $v$ a gradual valuation, the preordering induced by $v$ can be
directly used in order to compare, from the acceptability point of
view, an argument and its attackers\footnote{This idea is also used in
  the notion of ``defeat'' proposed by~\citeA{BC02}. So, there is a
  link between a ``well-defended argument'' and an argument which is
  not ``attacked'' in the sense of~\citeA{BC02} by its direct
  attackers. Note that, in the work of~\citeA{BC02}, the valuation is an extra
  knowledge added in the argumentation framework. In contrast, here,
  the $v$-preference is extracted from the attack graph.}.  This
defines a new class of acceptable arguments: well-defended arguments.

\begin{defin}[Well-defended argument]\label{def2}
  Consider $A \in \abo$, $A$ is {\em well-defended (for $v$)} if and
  only if $\forall B \in \abo$ such that $B \rbo A$, $B \not\succ A$.
\end{defin}

Thus, we capture the idea that an argument will be better accepted
 if it is at least as good as its direct attackers (or
incomparable with them in the case of a partial ordering). The set
of well-defended arguments will depend on the  valuation used.

Using this new notion, the set of the arguments is partitioned in
three classes:

\begin{monitem}
\item the first class contains the arguments which are not attacked,
\item the second class contains the arguments which are attacked but
  are well-defended,
\item the third class contains the other arguments (attacked and not
  well-defended).
\end{monitem}

Note that the set of the well-defended arguments corresponds to the
union of the two first classes.  A further refinement uses the gradual
valuation inside each of the classes as in Section~\ref{accep1}.

In Example~\ref{ex3} presented in Section~\ref{accep1}, the
well-defended arguments are:
\begin{monitem}
\item  $D$, $C_2$, $G$, $H$  and $A$ ($A$
is incomparable with $B$ but better than $E$) for the valuation with
tuples, 
\item though with the valuation of~\citeA{BH01} the
well-defended arguments are $D$, $C_2$, $G$, $I$ and $E$ ($E$ is better than
$A$).
\end{monitem}

Note also that, as in the semantics of~\citeA{Dung95},
Definition~\ref{def2} considers the attackers one by one. It is not
suitable for a valuation which handles the ``direct attack'' as a
whole (as the valuation of~\citeA{BH01} -- see the counterexamples
presented in Section~\ref{mixage}).


\subsection{Compatibility between  acceptability and gradual valuation}\label{mixage}
%*****************************************************************************

Following the previous sections, the set of arguments can be
partitioned in two different ways:

\begin{monitem}
\item First, given a semantics $S$ and a gradual valuation $v$, it is
  possible to use the partition issued from~\citeA{Dung95} which we
  have refined:

\centerline{\includegraphics[scale=0.4]{cmna4bis-angl.eps}}

\item Second, given a gradual valuation $v$, it is possible to use the
  partition induced by the notion of well-defended arguments:

\centerline{\includegraphics[scale=0.4]{cmna5ter-angl.eps}}

\end{monitem}

A very natural and interesting question is: is it possible to find a
semantics $S$ and a gradual valuation $v$ such that the associated
partitions have some compatibilities?

The following examples show that the class of the well-defended
arguments does not correspond to the class of the cleanly-accepted
arguments (in some cases, some uni-accepted arguments are even not
well-defended).


%*****************************************************************************
\subsubsection{Examples showing the non-compatibility in the general case}\label{exemples}
%*****************************************************************************

We give examples for each usual valuation (the global valuation with
tuples and 2 instances of the generic local
valuation:~\citeR{BH01,JV99}) and for the most classical semantics for
acceptability (preferred semantics and stable semantics of~\citeR{Dung95}).\\


{\em Cleanly-accepted argument but not well-defended:}
%*****************************************************************************
There are 3 examples (each using a distinct valuation: one for the
global valuation and two for the two well-known instances of the local
valuation):
\begin{monitem}
  
\item the argument $A$ is cleanly-accepted but it is not
  well-defended:

\centerline{\includegraphics[scale=0.8]{ex-pb-BH01-angl.eps}}

\item the argument $A$ is cleanly-accepted but it is not
  well-defended:

\centerline{\includegraphics[scale=0.8]{ex-pb-JV99-angl.eps}}

\item the argument $I$ is cleanly-accepted but it is not
  well-defended:

\centerline{\includegraphics[scale=0.8]{ex-pbbis-tuple-angl.eps}}
\end{monitem}

\ \\

{\em Well-defended argument but not cleanly-accepted:}
%*****************************************************************************
Similarly, for the same three valuations, we have:
\begin{monitem}
\item  the argument $C$ is well-defended but it is not cleanly-accepted:

\centerline{\includegraphics[scale=0.8]{ex-pb2-JV99-angl.eps}}

\item  the argument $F$ is well-defended  but it is not cleanly-accepted:

\centerline{\includegraphics[scale=0.8]{ex-pb2-BH01-angl.eps}}

\item  the argument $G$ is well-defended but it is not cleanly-accepted:

\centerline{\includegraphics[scale=0.8]{ex-pb2bis-tuple-angl.eps}}
\end{monitem}


%*****************************************************************************
\subsubsection{Particular cases leading to compatibility}\label{cas-particuliers}
%*****************************************************************************

In the context of an argumentation system with a finite relation
$\rbo$ without cycles\footnote{So, $(\abo, \rbo)$ is well-founded.},
the stable and the preferred semantics provide only one extension and
the levels of uni-accepted, exi-accepted, cleanly-accepted coincide.

In this context, there are at least two particular cases leading to
compatibility. \\ 

%*****************************************************************************
{\em First case:} It deals with the global valuation with tuples.



\begin{theo}\label{rac-dep}
  Let $\gbo$ be the graph associated with $\AR$, $\AR$ being an
  argumentation system with a finite relation $\rbo$ without cycles and
  satisfying the following condition: $\exists$ $A \in \abo$ such that
\begin{monitem}
\item $\forall X_i$, leaf of $\gbo$, $\exists$ only one path from
  $X_i$ to $A$, $X_i^1-\ldots-X_i^{l_i}-A$ with $X_i^1 = X_i$ and
  $l_i$ the length of this path (if $l_i$ is even, this path is a
  defence branch for $A$, else it is an attack branch),
\item all the paths from $X_i$ to $A$ are root-dependent in $A$,
\item $\forall A_i \in \abo$, $\exists X_j$ a leaf of $\gbo$ such that
  $A_i$ belongs to a path from $X_j$ to $A$.
\end{monitem}

Let $v$ be a valuation with tuples. Let $S$ be a semantics $\in$
\{preferred, stable\}.

\begin{enumerate}
\item $\forall B \in \abo$, $B \neq A$, $B$ (exi, uni, cleanly)
  accepted for $S$ iff $B$ well-defended for $v$.
\item If $A$ is (exi, uni, cleanly) accepted for $S$ then $A$ is
  well-defended for $v$ (the converse is false).
\item  If $A$ is well-defended for $v$ and if all the branches leading to $A$
  are defence branches for $A$ then $A$ is (exi, uni, cleanly) accepted  for $S$.
\end{enumerate}
\end{theo}



Note that Theorem~\ref{rac-dep} is, in general, not satisfied by a
local valuation. See the following counterexample for the valuation
of~\citeA{BH01}:

\centerline{\includegraphics[scale=0.6]{cex-rac-dep.eps}}

The graph satisfies the condition stated in Theorem~\ref{rac-dep}. The
set of well-defended arguments is $\{C_1, C_2, C_3\}$ (so, $A$ is not
well-defended). Nevertheless, $\{C_1, C_2,
C_3, A\}$ is the preferred extension.\\


%*****************************************************************************
{\em Second case:} This second case concerns the generic local
valuation:

\begin{theo}\label{prop-second-cas}
  Let $\AR$ be an argumentation system with a finite relation $\rbo$
  without cycles. Let $S$ be a semantics $\in$ \{preferred, stable\}.
  Let $v$ be a generic local valuation satisfying the following
  condition $(*)$:

\centerline{$(\forall i = 1 \ldots n, g(x_i) \geq x_i) \Rightarrow (g(h(x_1, \ldots,
x_n))  \geq h(x_1, \ldots, x_n))$\hspace*{2cm}$(*)$}

$\forall A \in \abo$, $A$ (exi, uni, cleanly) accepted for $S$ iff $A$
well-defended for  $v$.
\end{theo}

This theorem is a direct consequence of the following lemma:

\begin{lemme}\label{lem}
  Let $\AR$ be an argumentation system with a finite relation $\rbo$
  without cycles. Let $S$ be a semantics $\in$ \{preferred, stable\}.
  Let $v$ be a generic local valuation satisfying the condition $(*)$.
  \begin{description}
  \item[$(i)$]  If $A$ is exi-accepted and $A$ has
    only one direct attacker $B$ then $A \succeq B$.
    
  \item[$(ii)$]  If $B$ is not-accepted and $B$ has
    only one direct attacker $C$ then $C \succeq B$.
  \end{description}
\end{lemme}


\paragraph{Remark:} The condition  $(*)$ stated in Theorem~\ref{prop-second-cas} is:
\begin{monitem}
\item false for the local valuation proposed by~\citeA{BH01} as shown
  in the following graph:


\centerline{\includegraphics[scale=0.6]{cex-rac-dep.eps}}

We know that $g(x) = \frac{1}{1+x}$ and $h(x_1,\ldots,x_n) =
\Sigma_{i=1}^nx_i$ (see Property~\ref{prop-lien-BH01}). We get:
\begin{monitem}
\item $\forall i = 1\ldots 3$, $x_i = v(B_i) = 0.5$, 
\item $\forall i = 1\ldots 3$, $g(x_i) = 0.66$, so $g(x_i) \geq x_i$,
\item and nevertheless $g(h(x_1,x_2,x_3)) = v(A) = 0.4 \not\geq
  h(x_1,x_2,x_3) = 1.5$.
\end{monitem}

\item false for the local valuations defined with $h$ such that
  $\exists n > 1$ with $h(x_1,\ldots, x_n) > \max(x_1,\ldots, x_n)$
  (for all the functions $g$ strictly non-increasing): see the
  previous graph where $h(x_1,x_2,x_3) = 1.5$ and $\max(x_1,x_2,x_3) =
  0.5$.
  
\item true for the local valuations defined with $h = \max$ (for all
  the functions $g$): if $h = \max$ then $g(h(x_1,\ldots,x_n)) =
  g(\max(x_1,\ldots,x_n)) = g(x_j)$, $x_j$ being the maximum of the
  $x_i$; and, by assumption, $g(x_i) \geq x_i$, $\forall x_i$, so in
  particular for $x_j$; so, we get:
  
  \centerline{$g(h(x_1,\ldots,x_n)) = g(x_j) \geq x_j =
    \max(x_1,\ldots,x_n) = h(x_1,\ldots,x_n)$.}
\end{monitem}



%*****************************************************************************
\section{Conclusion}\label{conclusion}
%*****************************************************************************

In this paper, we have introduced graduality in the two main related
issues of argumentation systems:

\begin{monitem}
\item the valuation of the arguments,
\item the acceptability of the arguments.
\end{monitem}

Regarding the first issue, we have defined two formalisms introducing
an interaction-based gradual valuation of arguments.
  \begin{monitem}
  \item First, a generic gradual valuation which covers existing
    proposals (for example~\citeR{BH01} and~\citeR{JV99}). This approach
    is essentially ``local'' since it computes the value of the
    argument only from the value of its direct attackers.
  \item Then, an approach based on a labelling which takes the form of
    a pair of tuples; this labelling memorises the structure of the
    graph representing the interactions (the ``attack graph''),
    associating each branch with its length (number of the edges from
    the leaf to the current node) in the attack graph (if the length
    of the branch is an even integer, the branch is a defence branch
    for the current node, otherwise the branch is an attack branch for
    the current node). This approach is said to be ``global'' since it
    computes the value of the argument using the whole attack graph
    influencing the argument.
    \end{monitem}
    
    We have shown that each of these valuations induces a preordering
    on the set of the arguments, and we have brought to light the main
    differences between these two approaches.

\vspace{0.5cm}


Regarding the second issue, two distinct approaches have been
proposed:
\begin{monitem}
\item First, in the context of the collective acceptability
  of~\citeA{Dung95}: three levels of acceptability (uni-accepted,
  exi-accepted, not-accepted) were already defined. More graduality
  can be introduced in the collective acceptability using the notion
  of \emph{cleanly-accepted} arguments (those whose direct attackers
  are not-accepted).
  
\item Then, in the context of individual acceptability: using the
  previously defined gradual valuations, the new notion of
  \emph{well-defended} arguments has been introduced (those which are
  preferred to their direct attackers in the sense of a given gradual
  valuation $v$).
\end{monitem}

The first concept induces a refinement of the level of exi-accepted in
two sublevels (cleanly-accepted arguments and only-exi-accepted
arguments).  The gradual valuation allows graduality inside each level
of this collective acceptability.

The second concept induces two new levels of acceptability
(well-defended arguments and not-well-defended arguments).  The
gradual valuation also allows graduality inside each level of this
individual acceptability.

Regarding our initial purpose of introducing graduality in the
definition of acceptability, we have adopted a basic principle:
\begin{monitem}
\item acceptability is strongly related to the interactions between
  arguments (represented on the graph of interactions),
\item and an argument is all the more acceptable if it is preferred to
  its direct attackers.
\end{monitem}

Then, we have followed two different directions. One is based on a
refinement of an existing partition and remains in the framework of
Dung's work. The other one is based on the original concept of ``being
well-defended'', and deserves further investigation, in particular
from a computational point of view.

%Unfortunately, we
%noted on various examples that, in the general case, these levels were
%not compatible with those proposed by~\citeA{Dung95} and refined using
%the first concept (clean acceptability); and that, although the
%concepts of well-defended argument and cleanly-accepted argument are
%both built starting from:
%\begin{monitem}
%\item the interactions between arguments,
%\item and the same basic idea: in order to be selected, the argument
%  must be ``better'' than its direct attackers.
%\end{monitem}
%The difference between these notions comes from the chosen definition
%for the condition ``to be better than''.


%Some particular cases on which compatibility exists were identified.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%    Remerciements
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgements}

Thanks to the reviewers for their very interesting and constructive
comments.

Thanks to Thomas {\sc Schiex} for his help. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%   ANNEXE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section{The proofs}\label{annexe}


In this section, we give the proofs of all the properties presented in
Sections~\ref{eval-grad} and~\ref{acceptabilite}.

\begin{preuve} {\bf (of Property~\ref{prop-de-g})}
 By induction from $V_{\mbox{\scriptsize Min}} \leq
 g(V_{\mbox{\scriptsize Max}}) < V_{\mbox{\scriptsize Max}}$ and
  by  applying function $g$  twice.
\end{preuve}


\begin{preuve}  {\bf (of Property~\ref{prop-pre-ordre-total})}
The valuation function $v$ associates each argument $A$ with a value
$v(A)$ belonging to a set $V$ which is a subset of a completely ordered set $W$.
\end{preuve}


\begin{preuve}  {\bf (of Property~\ref{prop-val-circuit})}
Let $\cbo = A_n-A_{n-1}-\ldots-A_2-A_1$ be a cycle:
\begin{monitem}
\item If $n$ is even: $n = 2k$ and $v(A_1) = g(v(A_2)) = \ldots =
  g^{2k-1}(v(A_{2k})) = g^{2k}(v(A_1))$; so, $v(A_1)$ is a
  fixpoint of $g^{2k} = g^n$. It is  the same for each $A_i$, $1 \leq i \leq 2k$. 

However, the $A_i$ may have different values: for
example, for $n=2$, with the valuation of~\citeA{JV99},  $v(A_1) =
+$ and $v(A_2) = -$ with $g(+) = -$ and $g(-) = +$.
If all the $A_i$ have the same value, then this value will be a
fixpoint of $g$ (because $v(A_1) = g(v(A_2)) = g(v(A_1))$).

\item If $n$ is odd: $n = 2k+1$ and $v(A_1) = g(v(A_2)) = \ldots =
  g^{2k}(v(A_{2k+1})) = g^{2k+1}(v(A_1))$; so, $v(A_1)$ is a
  fixpoint of $g^{2k+1} = g^n$. It is  the same  for each $A_i$, $1 \leq i \leq 2k+1$.

Since the function $g$ is non-increasing, the function $g^{2k+1}$
is also non-increasing and we can apply the following result: ``if a
non-increasing function has fixpoints, these fixpoints are
identical''\footnote{Proof: let $g$ 
  be a non-increasing function, let $\alpha$ and $\beta$ be two fixpoints of
  $g$. If $\alpha \neq \beta$, we may suppose that $\alpha >
  \beta$, so $g(\alpha) \leq g(\beta)$ (since $g$ is non-increasing), so $\alpha \leq
  \beta$ (since $\alpha$ and $\beta$ are fixpoints of $g$), which is in
  contradiction with the assumption $\alpha >
  \beta$.}.
So, $v(A_1) = \ldots = v(A_{2k+1})$. But, $v(A_1) = g(v(A_2)) =
g(v(A_1))$, so $v(A_1)$ is a fixpoint of $g$.

So, for all the $1 \leq i \leq 2k+1$, $v(A_i)$ is a fixpoint of $g$.
\end{monitem}
\end{preuve}


\begin{preuve} {\bf (of Property~\ref{prop-principes-eval-loc})}\ \\
{\bf P1} is satisfied because: $\forall A \in \abo$,    if $A$ has no direct
attacker ($\rbo^-(A)$ is empty), then $v(A) = V_{\mbox{\scriptsize 
    Max}}$ and $g(V_{\mbox{\scriptsize Max}}) < V_{\mbox{\scriptsize Max}}$.

{\bf P2} is satisfied because if $\rbo^-(A) = \{A_1, \ldots, A_n\}$, $h
(v(A_1),\ldots, v(A_n))$ evaluates the ``direct attack'' of $A$.

{\bf P3} is satisfied because the function $g$ is supposed to be non-increasing.

{\bf P4} is satisfied due to the properties of the function $h$.
\end{preuve}


\begin{preuve}  {\bf (of Property~\ref{prop-lien-JV99})}
The valuation proposed by~\citeA{JV99} is the following:

Let $\deb\abo, \rbo\fin$ be an argumentation system. 
A complete labelling of $\deb\abo, \rbo\fin$ is a function $Et:
\abo  \to \{+, ?, -\}$ such that:
\begin{enumerate}
\item  If $Et(A) \in \{ ?, -\}$ then     $\exists B \in
  \rbo^-(A)$ such that $Et(B) \in \{+, ?\}$
\item If $Et(A) \in \{+, ?\}$ then     $\forall B \in
  \rbo^-(A)$ or $\in  \rbo^+(A)$, $Et(B) \in \{ ?, -\}$
\end{enumerate}

Moreover,~\citeA{JV99} also define a complete rooted labelling $Et$ with: $\forall A \in
\abo$,  if $Et(A) = -$ then $\exists B \in \rbo^-(A)$ such that $Et(B) = +$.

The translation of $Et$ into a local gradual valuation is very easy:

$g$ is defined by $g(-) = +$, $g(+) = -$, $g(?) = ?$ and $h$ is the function $\max$.
\end{preuve}



\begin{preuve}  {\bf (of Property~\ref{prop-lien-BH01})}
\citeA{BH01} introduce the following function $Cat$ (in the context of ``deductive''
arguments and for an acyclic graph):
\begin{monitem}
 \item         if $\rbo^-(A) = \emptyset$, then $Cat(A) = 1$
 \item         if $\rbo^-(A) \neq \emptyset$ with $\rbo^-(A) = \{A_1, \ldots,
          A_n\}$, $Cat(A) = \frac{1}{1 + Cat(A_1) + \ldots + Cat(A_n)}$
\end{monitem} 

The translation of $Cat$ into a gradual valuation is: $V = [0, 1]$, $W = [0, \infty[$, $V_{\mbox{\scriptsize Min}} = 0$ and $V_{\mbox{\scriptsize Max}} = 1$
and $g: W \to V$ is defined by $g(x) = \frac{1}{1 + x}$
and $h$ is defined by $h(\{x_1, \ldots, x_n\}) = x_1 + \cdots + x_n$.
\end{preuve}



\begin{preuve}  {\bf (of Property~\ref{comm-assoc})}
Let $t=(x_1, \ldots, x_n, \ldots)$, $t'=(y_1, \ldots, y_n, \ldots)$, $t''=(z_1, \ldots, z_n,
\ldots)$ be tuples.

\begin{description}
\item[Commutativity of $\star$: $t \star t' = t' \star t$] There are two cases:
  \begin{monitem}
  \item if $t$ or $t'$ $=$ $0^{\infty}$, the property is given by 
    Definition~\ref{oper-tuple}.
  \item if  $t$ and $t'$ $\neq$ $0^{\infty}$:
    \begin{eqnarray*}
      t \star t' & = & \sort(x_1, \ldots, x_n, \ldots, y_1, \ldots, y_n, \ldots) \\
       & = & \sort(y_1, \ldots, y_n, \ldots, x_1, \ldots, x_n, \ldots) \\
       & = & t' \star t
    \end{eqnarray*}
  \end{monitem}
\item[Associativity of $\star$: $(t \star t') \star t'' = t \star (t' \star t'')$]  There are two cases:
  \begin{monitem}
  \item if $t$ or $t'$ or $t''$ $=$ $0^{\infty}$, we can simplify the
    expression. For example, if $t = 0^{\infty}$:
    \begin{eqnarray*}
      (t \star t') \star t'' & =  & t' \star t'' \\
         & = & t \star (t' \star t'')
    \end{eqnarray*}
  \item if  $t$, $t'$ and $t''$ $\neq$ $0^{\infty}$:
    \begin{eqnarray*}
      (t \star t') \star t'' & = & \sort(x_1, \ldots, x_n, \ldots, y_1, \ldots, y_n, \ldots, z_1,
      \ldots, z_n, \ldots) \\
       & = & t \star (t' \star t'')
    \end{eqnarray*}
  \end{monitem}
\item[Property of $\oplus$: $(t \oplus k) \oplus k' = t \oplus (k+k')$] We have:
  \begin{eqnarray*}
    (t \oplus k) \oplus k' & = & (x_1 + k, \ldots, x_n + k, \ldots) \oplus k' \\
       & = & (x_1 + k + k', \ldots, x_n + k + k', \ldots) \\
       & = &  t \oplus (k+k')
  \end{eqnarray*}
\item[Distributivity: $(t \star t') \oplus k = (t \oplus k) \star (t' \oplus k)$] We have:
  \begin{eqnarray*}
    (t \star t') \oplus k & = & \sort(x_1, \ldots, x_n, \ldots, x'_1, \ldots, x'_n, \ldots) \oplus k \\
       & = & \sort(x_1 + k, \ldots, x_n + k, \ldots, x'_1 + k, \ldots, x'_n + k, \ldots) \\
       & = &  (t \oplus k) \star (t' \oplus k)
  \end{eqnarray*}
\end{description}
\end{preuve}


\begin{preuve}  {\bf (of Property~\ref{prop-preordre})}
First, we show that the relation $\succeq$ defined by 
Algorithm~\ref{compar-tuple3} is a partial ordering:

\begin{quote}
  Let $u$, $v$, $w$ be three tupled values, the relation $\succeq$
  defined by Algorithm~\ref{compar-tuple3} is: 
\begin{monitem}
\item reflexive: $u \succeq u$ because $u = u$, so $u \succeq
  u$ AND $u \succeq u$ (case 1 of
  Algorithm~\ref{compar-tuple3});
\item transitive: suppose that $u \succeq v$ and $v \succeq w$ and
  consider all the possible cases:
  \begin{monitem}
  \item if $u = v$:
    \begin{monitem}
    \item if $v = w$: then $u = w$ so $u \succeq
      w$,
    \item if $|v_i| \leq |w_i|$ AND $|v_p| > |w_p|$: 
      then $|v_i| = |u_i| \leq |w_i|$ AND $|v_p| = |u_p| >
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| < |w_i|$ AND $|v_p| \geq |w_p|$: 
      then $|v_i| = |u_i| < |w_i|$ AND $|v_p| = |u_p| \geq
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| = |w_i|$ AND $|v_p| = |w_p|$ AND
      $v_p \leq_{lex\infty} w_p$ AND $v_i \geq_{lex\infty} w_i$: then
      $|v_i| = |u_i| = |w_i|$ AND $|v_p| = |u_p| =
      |w_p|$ AND $v_p = u_p \leq_{lex\infty} w_p$ AND $v_i =
      u_i \geq_{lex\infty} w_i$, so $u \succeq w$;
    \end{monitem}
    
  \item if $|u_i| \leq |v_i|$ AND $|u_p| > |v_p|$:
    \begin{monitem}
    \item if $v = w$: then $|u_i| \leq |v_i| =
      |w_i|$ AND $|u_p| > |v_p| = |w_p|$ so $u \succeq
      w$,
    \item if $|v_i| \leq |w_i|$ AND $|v_p| > |w_p|$: 
      then $|u_i| \leq |v_i| \leq |w_i|$ AND $|u_p| > |v_p| >
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| < |w_i|$ AND $|v_p| \geq |w_p|$: 
      then $|u_i| \leq |v_i| < |w_i|$ AND $|u_p| > |v_p| \geq
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| = |w_i|$ AND $|v_p| = |w_p|$: 
      then $|u_i| \leq |v_i| = |w_i|$ AND $|u_p| > |v_p| =
      |w_p|$, so $u \succeq w$;
    \end{monitem}
    
  \item if $|u_i| < |v_i|$ AND $|u_p| \geq |v_p|$:
    \begin{monitem}
    \item if $v = w$: then $|u_i| < |v_i| =
      |w_i|$ AND $|u_p| \geq |v_p| = |w_p|$ so $u \succeq
      w$,
    \item if $|v_i| \leq |w_i|$ AND $|v_p| > |w_p|$: 
      then $|u_i| < |v_i| \leq |w_i|$ AND $|u_p| \geq |v_p| >
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| < |w_i|$ AND $|v_p| \geq |w_p|$: 
      then $|u_i| < |v_i| < |w_i|$ AND $|u_p| \geq |v_p| \geq
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| = |w_i|$ AND $|v_p| = |w_p|$: 
      then $|u_i| < |v_i| = |w_i|$ AND $|u_p| \geq |v_p| =
      |w_p|$, so $u \succeq w$;
    \end{monitem}
    
  \item if $|u_i| = |v_i|$ AND $|u_p| = |v_p|$ AND $u_p
    \leq_{lex\infty} v_p$ AND $u_i \geq_{lex\infty} v_i$:
    \begin{monitem}
    \item if $v = w$: then $|u_i| = |v_i| =
      |w_i|$ AND $|u_p| = |v_p| = |w_p|$ AND $u_p
      \leq_{lex\infty} v_p = w_p$ AND $u_i \geq_{lex\infty} v_i = w_i$
      so $u \succeq w$,
    \item if $|v_i| \leq |w_i|$ AND $|v_p| > |w_p|$: 
      then $|u_i| = |v_i| \leq |w_i|$ AND $|u_p| = |v_p| >
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| < |w_i|$ AND $|v_p| \geq |w_p|$: 
      then $|u_i| = |v_i| < |w_i|$ AND $|u_p| = |v_p| \geq
      |w_p|$, so $u \succeq w$,
    \item if $|v_i| = |w_i|$ AND $|v_p| = |w_p|$ AND
      $v_p \leq_{lex\infty} w_p$ AND $v_i \geq_{lex\infty} w_i$: then
      $|u_i| = |v_i| = |w_i|$ AND $|u_p| = |v_p| =
      |w_p|$ AND $u_p \leq_{lex\infty} v_p \leq_{lex\infty} w_p$ AND $u_i
      \geq_{lex\infty} v_i \geq_{lex\infty} w_i$, so $u \succeq w$.
    \end{monitem}
    In all cases, $u \succeq w$.
\end{monitem}
\end{monitem}
\end{quote}

Now, consider the maximal and minimal values:

\begin{monitem}
\item The tupled value $[0^{\infty},()]$ is the unique maximal element for the
  preordering $\succeq$: let $v$ be a tupled value such that $v \neq [0^{\infty},()]$, then
  $|v_p| \leq  \infty$ and $|v_i| \geq 0$. Compare $[0^{\infty},()]$ and $v$ with
  Algorithm~\ref{compar-tuple3}: $[0^{\infty},()] \neq v$ so the case number 1
  is not used; then, $|()| = 0 \leq |v_i|$ AND $|0^{\infty}| = \infty \geq 
  |v_p|$ so there are two cases:
  \begin{itemize}
  \item if $|v_p| =  \infty$ and $|v_i| = 0$, the case 3 of 
    Algorithm~\ref{compar-tuple3} is applied and  $[0^{\infty},()] \succ  v$,
  \item else $|v_p| \leq  \infty$ and $|v_i| \geq 0$, the case 5 of 
    Algorithm~\ref{compar-tuple3} is applied and $[0^{\infty},()] \succ v$.
  \end{itemize}  

\item  The tupled value $[(),1^{\infty}]$ is the unique minimal element for the
  preordering $\succeq$: let $v$ be a tupled value such that $v \neq [(),1^{\infty}]$, then
  $|v_i| \leq  \infty$ and $|v_p| \geq 0$. Compare $[(),1^{\infty}]$ and $v$ with
  Algorithm~\ref{compar-tuple3}: $[(),1^{\infty}] \neq v$ so the case number 1
  is not used; then, $|()| = 0 \leq |v_p|$ AND $|1^{\infty}| = \infty \geq 
  |v_i|$ so there are two cases:
  \begin{itemize}
  \item if $|v_i| =  \infty$ and $|v_p| = 0$, the case 2 of
    Algorithm~\ref{compar-tuple3} is applied and  $[(),1^{\infty}] \prec  v$,
  \item else $|v_i| \leq  \infty$ and $|v_p| \geq 0$, the case 6 of
    Algorithm~\ref{compar-tuple3} is applied and $[(),1^{\infty}] \prec  v$.
  \end{itemize} 
\end{monitem}
\end{preuve}


\begin{preuve}  {\bf (of Property~\ref{prop-principe-tuple})}
The principle {\bf P1$'$} is satisfied by  Definition~\ref{def-nelle-eval-tuple}
and by the fact that $[0^{\infty},()]$ is the unique maximal element of $v(\abo)$ (see Property~\ref{valmaxminpreordre}).

The principle {\bf P2$'$} is satisfied because of Definition~\ref{def-nelle-eval-tuple}. 

The principles {\bf P3$'$} and {\bf P4$'$} are satisfied: all the
possible cases of improvement/degradation of the
defence/attack for a given
argument (see Definition~\ref{def3-ame-det-def-att}) are applied case
by case\footnote{We work case by case in order to avoid the complex
  cases in which we have several simultaneous simple
  modifications. For example, the modification of the length of a
  branch which 
  changes the status of the branch (an even integer replaced by an odd
  integer) is a complex case corresponding to two simple cases: the
  removal of a branch with a given status, then the addition of a new
  branch with a different status.}. Each case leads to a new
argument. Using Algorithm~\ref{compar-tuple3}, the
comparison between the argument before  and
after the application of the case shows that the
principle {\bf P3$'$} (or {\bf P4$'$}, depending on the applied case) is satisfied.  
\end{preuve}



\begin{preuve}  {\bf (of Property~\ref{prop-ind-branches})}
From Definition~\ref{def-nelle-eval-tuple}.
\end{preuve}


\begin{preuve}  {\bf (of Property~\ref{non-att-ext-pref})}
First, we consider the case of the preferred extensions:
Let $E$ be a preferred extension $\subseteq \abo$, we assume that $E$ does not
contain all the unattacked arguments of $\abo$. So, let $A \in \abo$ be
an unattacked argument such that $A \not\in E$.\\
Consider $E \cup \{A\}$:
\begin{monitem}
\item If $E \cup \{A\}$ is conflict-free then, with $A$ an unattacked
  argument and $E$ a preferred extension, $E \cup \{A\}$ collectively
  defends itself, so $E \cup \{A\}$ is admissible and $E \subseteq E
  \cup \{A\}$. This contradicts the fact that $E$ is a preferred extension.
\item If $E \cup \{A\}$ contains at least one conflict, then:
  \begin{monitem}
  \item $\exists B \in E$ such that $B \rbo A$. This is impossible since $A$
    is unattacked.
  \item or  $\exists B \in E$ such that $A \rbo B$. But, since $A$ is
    unattacked, $\nexists C \in E$ such that $C \rbo A$. So,
    $E$ does not collectively defend  $B$, which is in 
    contradiction with the fact that $E$ is a preferred extension.
  \end{monitem}
\end{monitem}
So, the assumption ``$E$ does not contain all the unattacked
arguments of $\abo$'' cannot hold.

Now, we consider  stable extensions:
Let $E$ be a stable extension  $\subseteq \abo$, we assume that $E$ does not
contain all the unattacked arguments of $\abo$. So, let $A \in \abo$ be
an unattacked argument such that $A \not\in E$.\\
Since $A \not\in E$ there exists in $E$ another argument
$B$ which attacks $A$; This is impossible since $A$ is unattacked.\\
So,  the assumption ``$E$ does not contain all the unattacked
arguments of $\abo$'' cannot hold.
\end{preuve}



\begin{preuve}  {\bf (of Property~\ref{prop-uni-acc-prop-acc})}
An argument and one of its direct attackers cannot belong to the same
extension in the sense of~\citeA{Dung95} because  the extension must
be conflict-free. So,
since $A$ is uni-accepted, it means that $A$ belongs to all the 
extensions, and none of the direct attackers of $A$ belongs to these
extensions. 

For the converse, we use the following counterexample in the case
of the preferred semantics:

\begin{tabular}{c c}
  \begin{minipage}{6cm}
    \centerline{\includegraphics[scale=0.55]{cex-ba-uni.eps}}
\end{minipage} &
\begin{minipage}{6.5cm}
  There are two preferred extensions $\{K,H,G\}$ and $\{A,E,K,H\}$.
  The argument $A$ is cleanly-accepted ($B$ and $C$ do not belong to
  any preferred extension, and $A$ belongs to at least one of the two
  extensions). But, $A$ is not uni-accepted because it does not belong
  to all preferred extensions.
\end{minipage}
\end{tabular}
\end{preuve}

\begin{preuve} {\bf (of Property~\ref{uni-prop-stable})}
First, $A$ uni-accepted $\Rightarrow$ $A$
cleanly-accepted is the result of Property~\ref{prop-uni-acc-prop-acc}.

Conversely, let $A$ be a cleanly-accepted argument, there exists at least
one stable extension $E$ such that $A \in E$ and $\forall B, B \rbo A$, $B
\not\in E'$, $\forall E'$ stable extension. Using a {\it reductio ad
  absurdum}, we assume that there exists a stable extension 
$E''$ such that $A
\not\in E''$; but, if $A \not\in E''$, it means that $\exists B
\in E''$ such that $B \rbo A$, so, the direct attacker $B$ of $A$
belongs to a stable extension; so, there is a contradiction with the
assumption ($A$ is
cleanly-accepted); so, $E''$ does not exist and $A$ is uni-accepted.
\end{preuve}


\begin{preuve}  {\bf (of Theorem~\ref{rac-dep})}\ \\
  \begin{enumerate}
  \item We consider the arguments $B \in \abo$ such that $B
    \neq A$.  Let
    $X_i$ be a leaf, the path $\cbo \in \cbo(X_i,A)$ is
    $X_i^1-\ldots-X_i^{l_i}-A$ with $X_i^1 = X_i$ and $l_i$ denoting
    the length of the path (if $l_i$ is even, this path is a defence
    branch for $A$, else it is an attack branch).
    
    The constraints from $X_i^1$ to $X_i^{l_i}$ are the following:
    
    $$X_i^1 \succ X_i^3 \succ \ldots \succ X_i^{l_i} \succ X_i^{l_i-1} \succ \ldots \succ
    X_i^4 \succ X_i^2 \mbox{ if }l_i \mbox{ odd
    }\geq 1$$
    or
    $$X_i^1 \succ X_i^3 \succ \ldots \succ X_i^{l_i-1} \succ X_i^{l_i}
    \succ \ldots \succ X_i^4 \succ X_i^2 \mbox{ if }l_i \mbox{
      even }\geq 2$$
    
    So, for the path $X_i^1-\ldots-X_i^{l_i}$, the set of the
    well-defended arguments is $\{X_i^1, X_i^3, \ldots, X_i^{l_i}\}$
    if $l_i$ is odd, $\{X_i^1, X_i^3, \ldots, X_i^{l_i-1}\}$ otherwise
    (this is the set of all the arguments having a value strictly
    better than those of their direct attackers).  This set will
    denoted by {\sc Accep}$_i$.
    
    By definition, this set is conflict-free, it defends all its
    elements (because it contains only the leaf of the path and all
    the arguments which are defended by this leaf) and it attacks all
    the other arguments of the path. If we try to include another
    argument of the path $X \in \{X_i^1, \ldots, X_i^{l_i}\}
    \setminus$ {\sc Accep}$_i$, we obtain a conflict (because {\bf
      all} the other arguments of the path are attacked by the
    elements of {\sc Accep}$_i$). So, for $\{X_i^1, \ldots,
    X_i^{l_i}\}$, {\sc Accep}$_i$ is the only preferred and stable extension.
    
    Consider $\abo' = \abo \setminus \{A\}$, with $\rbo'$ being the
    restriction of $\rbo$ to $\abo'$\footnote{$\rbo'$ is the
      restriction of $\rbo$ to $\abo'$ if and only if $\rbo' = \{(a,b)
      | a \rbo b, a \in \abo', b \in \abo'\}$.} and {\sc Union\_} {\sc
      Accep}$=\cup_i$ {\sc Accep}$_i$, then {\sc Union\_Accep} is the only
    preferred and stable extension of $\deb\abo', \rbo'\fin$.

    So, $\forall B \in\abo, B \neq A$, $B$ is accepted iff $B$
    well-defended.

\item Now, consider $A$. If $A$ is accepted then {\sc Union\_Accep} $\cup
  \{A\}$ is  the only
    preferred and stable extension of $\AR$. So, $\forall i$,
    $X_i^{l_i}$ does not belong to the extension. Then, $\forall i$, $X_i^{l_i-1} \succ
    X_i^{l_i}$. Therefore, each branch leading to $A$ is a defence branch for
    $A$. So, $\forall i$, $v(X_i^{l_i}) = [()(l_i-1)]$. So, $v(A) =
    [(l_1, l_2, \ldots, l_n)()]$. Then, $\forall i$, $v(A) \succ
    v(X_i^{l_i})$. Therefore, $A$ is well-defended.

    Using the following example, we show that the converse is false:

\centerline{\includegraphics[scale=0.6]{cex-rac-dep2.eps}}

$A$ is well-defended ($A \succ B_1$, $A \succ B_2$ and $A$ is
incomparable with $A_1$) but not accepted.

\item  Now, if $A$ is well-defended and all the branches leading to
  $A$ are defence branches for $A$, then {\sc Union\_Accep} $\cup
  \{A\}$ is conflict-free and $A$ is defended against each of its
  direct attackers (because $X_i^{l_i-1} \in$ {\sc Union\_Accep} for
  each branch $i$).  So, {\sc Union\_Accep} $\cup \{A\}$ is the
  preferred and stable extension of $\AR$ and $A$ is accepted.
\end{enumerate}
\end{preuve}



\begin{preuveL}  {\bf (of Lemma~\ref{lem})}
Let $\AR$ be an argumentation system with a finite relation $\rbo$
without cycles (so, there is only one non empty preferred and stable   
extension denoted by $E$). We know that:

\begin{monitem}
\item if $A$ is exi-accepted and if $A$ has a direct attacker denoted
  by $B$ then $B$ is not-accepted, 
\item if $B$ is not-accepted then there exists at least one argument
  $C$ such that $C \rbo
  B$ and $C$ is exi-accepted (because $B$ does not belong to
  $E$ and $E$ is stable, so $C$ must $\in E$). So,
  {\it a fortiori}, if $B$ is not-accepted and has only one direct
  attacker $C$, then $C$ will be exi-accepted.
\end{monitem}

The proof is done by induction on the depth of a proof tree for
$A$ or $C$.

\begin{monitem}
\item Basic case for $(i)$: $A$ is exi-accepted with only
  one direct attacker $B$ ($B \rbo A$) and $C_1
  \ldots C_n$ are the direct attackers of $B$; so, we have a proof tree whose
  depth is 2 for $A$
  and one of the unattacked $C_i$, for example $C_1$; so:

  \begin{eqnarray*}
    v(B) & = & g(h(v(C_1), \ldots, v(C_n)))\\
         & \leq & g(v(C_1)) \tab \mbox{because }h(v(C_1), \ldots,
         v(C_n)) \geq h(v(C_1)) = v(C_1)\\
         &  & \tab \tab \mbox{ and }g \mbox{ is
           non-increasing}\\
         & \leq & g(V_{\mbox{\scriptsize Max}})\tab \mbox{ because }v(C_1) = V_{\mbox{\scriptsize Max}}
  \end{eqnarray*}

so:

\begin{eqnarray*}
  v(A) & = & g(v(B)) \\
       & \geq & g^2(V_{\mbox{\scriptsize Max}})
\end{eqnarray*}

But, Property~\ref{prop-de-g} says that $g^2(V_{\mbox{\scriptsize Max}}) \geq
g(V_{\mbox{\scriptsize Max}})$, so $v(A) \geq v(B)$.

\item Basic case for $(ii)$: $C \rbo B$ with $C$
  the only direct attacker of $B$; so, we have a proof tree whose
  depth is 0 for $C$, {\it i.e.} $C$ is unattacked; so, $v(C) = V_{\mbox{\scriptsize Max}}$ and
  $v(B) = g(V_{\mbox{\scriptsize Max}}) \leq v(C)$ (following Definition~\ref{def-eval-generique}).

\item General case for $(i)$: $A$ is exi-accepted with only
  one direct attacker $B$ ($B \rbo A$) and $C_1
  \ldots C_n$ are the direct attackers of $B$, with one of the $C_i$ exi-accepted, for
  example $C_1$; we consider the subgraph leading to $C_1$ to which we add
  $C_1 \rbo B \rbo A$, and we assume:

\centerline{$g(v(C_1)) \leq v(C_1)$ (induction assumption issued from~$(ii)$)}

So:

  \begin{eqnarray*}
    v(B) & = & g(h(v(C_1), \ldots, v(C_n)))\\
         & \leq & g(v(C_1)) \tab \mbox{for the same reasons as
           in the basic case}\\
         & \leq & v(C_1)  \tab\tab \mbox{by induction assumption}\\
         & \leq & h(v(C_1), \ldots, v(C_n)) \tab \mbox{property of }h
  \end{eqnarray*}

and with the non-increasing of $g$:

\begin{eqnarray*}
  v(A) & = & g(v(B)) \\
       & \geq & g(h(v(C_1), \ldots, v(C_n))) = v(B)
\end{eqnarray*}


\item General case for $(ii)$: $B$ is not-accepted, so
  $C$ is exi-accepted; we assume that $C$ has several direct
  attackers $D_1 \ldots D_p$ which are all not-accepted
  (because $C$ is exi-accepted); we consider each subgraph leading to
  $D_i$ to which we add $D_i \rbo C \rbo B$ and we assume:

\centerline{$\forall i=1 \ldots p$, $g(v(D_i)) \geq
  v(D_i)$ (induction assumption issued from $(i)$)}

so:

\begin{eqnarray*}
  v(C) & = & g(h(v(D_1), \ldots, v(D_p))) \\
      & \geq & h(v(D_1), \ldots, v(D_p)) \tab \mbox{application of the
        condition }(*)\\
      & &  \tab \tab \tab \tab \mbox{since the induction assumption} \\
      & &   \tab \tab \tab\tab \mbox{corresponds to
        the premise of }(*)
\end{eqnarray*}

so:

\begin{eqnarray*}
  v(B) & = & g(v(C)) \\
      & \leq & g(h(v(D_1), \ldots, v(D_p))) = v(C)
\end{eqnarray*}
\end{monitem}
\end{preuveL}

\begin{preuve}  {\bf (of Theorem~\ref{prop-second-cas})}
Assume that $(*)$ is true and consider $A \in \abo$ which is
exi-accepted. Let $B_i$, $i = 1\ldots n$, be the direct attackers of $A$.
Then, for all $i= 1\ldots n$, in the subgraph leading to $B_i$
and completed with $B_i \rbo A$, we apply the lemma and we obtain:
$g(v(B_i)) \geq v(B_i)$, $\forall i= 1\ldots n$. Thus, we have:

\begin{eqnarray*}
v(A) & = & g(h(v(B_1), \ldots, v(B_n))) \\
 & \geq & h(v(B_1), \ldots, v(B_n)) \tab\mbox{ by applying  }(*)\\
 & \geq & v(B_i), \forall i = 1 \ldots n  \tab\mbox{ property of  }h
\end{eqnarray*}

So, $A$ is well-defended.

\vspace{0.2cm}

For the converse, let $A \in \abo$ be well-defended. Let $B_1,
\ldots, B_n$ be the direct attackers of $A$ and assume that $A$ is not
exi-accepted. Then, there exists at least one direct attacker $B_i$ of
$A$ such that $B_i$ is exi-accepted (because there is only one
preferred and stable extension). 
We can apply $(ii)$ of the lemma on the subgraph leading
to $B_i$ completed with $B_i \rbo A$ and we obtain $g(v(B_i)) \leq
v(B_i)$. So, there exists $B_i$ a direct attacker of $A$ such that:

\begin{eqnarray*}
  v(A) & = & g(h(v(B_1), \ldots, v(B_n))) \\
       & \leq & g(v(B_i))\tab\mbox{ property of  }h \mbox{ and
         non-increasing of }g\\
       & \leq & v(B_i)  \tab\mbox{ using the lemma  }
\end{eqnarray*}

This is in contradiction with $A$ well-defended. So, $A$ is exi-accepted.
\end{preuve}







%*****************************************************************************
\section{Computation of tupled values}
\label{algo-calcul-val-tuple}
%*****************************************************************************

We propose an algorithm for computing the tupled values for an arbitrary graph
(cyclic or acyclic, the cycles may be isolated or not). This
algorithm uses a principle of propagation of values: an argument
is evaluated when the values of its direct attackers are known. 

We must consider the cycles as meta-arguments which are
evaluated when all the ``direct attackers of the cycle'' ({\it i.e.}
the direct attackers of one of the elements of the cycle which do not
belong to the cycle) are evaluated. 

The beginning of the process is as follows: we consider that
all the arguments have the initial value
$[0^{\infty}, ()]$, and only the leaves of the graph are ``marked'' as having
their final values. Thus, we have the following  partition of the graph
$\gbo$:
\begin{monitem}
\item $\gbo_v$: the part of the graph already evaluated (at the beginning, this
  part contains only the leaves of the graph),
\item $\gbo_{\lnot v}$: the part of the graph which is not evaluated 
  (at the beginning, this part contains all the arguments of
  the graph $\gbo$ except the leaves).
\end{monitem}

The algorithm also relies on a special data
structure denoted by $\lbo$ giving the list of the cycles in the graph
and their main characteristics:
\begin{monitem}
\item list of the arguments which belong to this cycle,
\item list of the arguments which belong to this cycle and which have
  direct attackers outside the cycle (these arguments are called {\em
    inputs of the cycle}; those which will be used in order to
  propagate the values across the cycle in the case of a  non
  isolated cycle); this list will be empty in the case of an isolated cycle.
\end{monitem}

\paragraph{Remark:} For the sake of efficiency, the
interconnected cycles (see Definition~\ref{def-dung}) will be
considered as a ``whole'' by the algorithm and will be used like a
``meta-cycle''.
For example, the two cycles $A-B-A$ and $B-C-B$ which do not have any direct
attacker outside of the cycles, will be described in the data
structure $\lbo$ as only one ``meta-cycle'' with the following lists:
\begin{monitem}
\item $A$, $B$, $C$,
\item nothing (because it is an isolated ``meta-cycle'').
\end{monitem}

In order to avoid some ambiguity, these ``meta-cycles'' are defined as {\em mcycles}:

\begin{defin}[mcycle]
Let $\gbo$ be an attack graph. Let $\cbo\cbo$ be the set of all the
cycles of $\gbo$.  
Let $\cbo\cbo' \subseteq \cbo\cbo$ and $\cbo\cbo' = \{\cbo_1, \ldots, \cbo_n\}$
be a set of  cycles. 

Let $\abo_{\cbo\cbo'}$ be the  set: $\{A_j \mbox{ such that } \exists
    \cbo_i \in \cbo\cbo' \mbox{ and } A_j \in \cbo_i\}$.

If $\cbo\cbo'$ satisfies the following properties:
\begin{monitem}
  \item  $\forall A_j, A_k \in \abo_{\cbo\cbo'}$, $\exists$ a path from
    $A_j$ to $A_k$ such that each element (arguments or edges between
    arguments) of the path belongs to 
    cycles of $\cbo\cbo'$,

\item and $\forall \cbo_k \in \cbo\cbo \setminus \cbo\cbo'$,
    $\not\exists \cbo_i \in \cbo\cbo'$ such that $\cbo_k$ is interconnected with $\cbo_i$.
\end{monitem}

Then the union of the  $\cbo_i$ belonging to $\cbo\cbo'$ is a {\em mcycle}. 
\end{defin}

Thus, we make a partition of $\cbo\cbo$ using the
notion of interconnection between cycles, each element of the 
partition being a different {\em mcycle}.
See on the following example:

\centerline{\includegraphics[scale=0.7]{ex-mcircuit.eps}}

In this graph, there are 6 cycles:
\begin{monitem}
\item $\{J\}$,
\item $\{I,J,K\}$,
\item $\{K,L\}$,
\item $\{B,C,D\}$,
\item $\{C,E\}$,
\item $\{F,G\}$.
\end{monitem}

and 3 mcycles:
\begin{monitem}
\item $\{I,J,K,L\}$,
\item $\{B,C,D,E\}$,
\item $\{F,G\}$.
\end{monitem}


Algorithm~\ref{algo-gen} is the main algorithm used for computing
the tupled values. 

%%%%%%%%%%%%%%%%%%% ALGO-GEN %%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}
\small
\dontprintsemicolon
\SetVline
 \% {\bf Description of parameters:} \hfill \% \;
 \%  \tab $\gbo$: attack graph (partitioned
 in $\gbo_v$ and $\gbo_{\lnot v}$) \hfill \% \;
 \%  \tab $\lbo$: data structure describing the mcycles\hfill \% \;
 \%  \tab $n$: number of propagation steps for the mcycles \hfill \% \;
 \%  {\bf Used variables:} \hfill \% \;
 \%  \tab $A$: the current argument (to be evaluated)\hfill \% \;
 \%  \tab $\cbo$:  the current mcycle (to be evaluated) (containing $A$) \hfill \% \;
 \%  \tab $LAD$: list of the direct attackers of $\cbo$ \hfill \% \;
 \%  \tab $B_i$: the current direct attackers of $A$, or of $\cbo$\hfill \% \;
\Indm \BlankLine
\Begin {  
  \nl\While{there is at least one argument in $\gbo_{\lnot v}$}{
    \nl $A$ = {\sc Choose-Argument}($\gbo_{\lnot v}$) \;
    \nl\If {$A$ does not belong to a mcycle $\cbo$ described in $\lbo$}{
      \nl\If {$\forall B_i \in \rbo^-(A)$, $B_i$ is already evaluated}{
        \nl $\gbo_v$ = {\sc Add-Node}($\gbo_v$,{\sc Evaluate-Node}($A$,
        $\rbo^-(A)$, 1)) \hfill \% The value of $A$ \% \; 
        \hfill \% is the value of its \% \; 
        \hfill \% direct attackers \% \; 
        \hfill \% in which we add 1  \% \; 
        \hfill \% see Definition~\ref{def-nelle-eval-tuple} \% \; 
       \nl $\gbo_{\lnot v}$ = {\sc Remove-Node}($\gbo_{\lnot v}$, $A$)\;
      }
    }
    \nl\Else {
      \nl\If {$\cbo$ is isolated}{
        \nl $\gbo_v$ =  {\sc Add-Mcycle}($\gbo_v$,{\sc
          Evaluate-Mcycle-Isolated}($\gbo$, $\cbo$, $n$))\;
        \nl $\gbo_{\lnot v}$ = {\sc Remove-Mcycle}($\gbo_{\lnot v}$, $\cbo$)\;
      }
      \nl\Else {
       \nl $LAD$ = {\sc Find-Direct-Attackers-Mcycle}($\cbo$,
        $\gbo$)\;
       \nl \If {$\forall B_i \in LAD$, $B_i$ is already evaluated} {
        \nl  $\gbo_v$ = {\sc Add-Mcycle}($\gbo_v$,\;
\tab\tab{\sc
            Evaluate-Mcycle-Not-Isolated}($\gbo$, $\cbo$, $LAD$,$n$))\;
        \nl  $\gbo_{\lnot v}$ = {\sc Remove-Mcycle}($\gbo_{\lnot v}$, $\cbo$)\;
        }
      }
    }
  }
\nl\Return{$\gbo$}\;
}
\caption{Algorithm for computing tupled values\label{algo-gen}}
\end{algorithm}

The function {\sc Add-Node} (respectively {\sc Remove-Node}) whose
parameters are a subgraph $\gbo_x$ of the attack graph and a node $s$,
adds (resp. removes) $s$ in (resp. of) $\gbo_x$. The other
functions are described in~\cite{CLS03a}.

Algorithm~\ref{algo-gen} has been applied on an example
after the step of rewriting (see Figure~\ref{ex-rew}). Note that in
order to make the understanding of the results easier, we do not have
created new arguments (as in Definitions~\ref{rewrite-unattack-cyc}
and~\ref{rewrite-attack-cyc}), but of 
course, it would be necessary for a rigorous formalization.

\begin{figure}[htbp]
  \centerline{\includegraphics[scale=0.7]{fig1-jair.eps}}\centering
  
The previous argumentation graph can be rewritten as follows:

\centerline{\includegraphics[scale=0.7]{fig1-rew-jair.eps}}

The results of the valuation obtained after one propagation step are:

\begin{monitem}
\item $v(A) = [(0,\ldots, 0)()]$,
\item $v(B) = [(6,8,8,\ldots)(1,3,5,\ldots)]$,
\item $v(C) = [(2,4,6,\ldots)(5,\ldots)]$,
\item $v(D) = [(6,\ldots)(3,5,\ldots)]$,
\item $v(E) = [(4,6,\ldots)()]$,
\item $v(F) = [(8,\ldots)(3,5,5,7,7,\ldots)]$,
\item $v(G) = [(2,4,6,\ldots)(7,\ldots)]$,
\end{monitem}
  \caption{Example of rewriting}\label{ex-rew}  
\end{figure}

%\vskip 0.2in

\newpage

\bibliography{mcl}
\bibliographystyle{theapa}


\end{document}

  
