validation oxford

[hdrcouchot.git] / sdd.tex

\JFC{Chapeau chapitre à faire}



% Cette section énonce quelques notions suffisantes 
% à la compréhension de ce document.
% Elle commence par formaliser ce que sont les systèmes dynamiques booléens 
% (section \ref{sub:sdd}) 
% et montre comment en extraire leur graphe d'itérations (section~\ref{sub:grIter})
% et d'interactions (section~\ref{sub:sdd:inter}). 
% Elle se termine en définissant une distance sur l'espace 
% $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$ (section~\ref{sub:metric}).




On considère l'espace booléen 
$\Bool=\{0,1\}$
muni des opérateurs binaires 
de disjonction \og +\fg{},
de conjonction \og . \fg{} et
unaire de négation \og $\overline{\mathstrut\enskip}$ \fg{}.


Soit ${\mathsf{N}}$ un entier naturel.
On introduit quelques notations à propos d'éléments de $\Bool^{\mathsf{N}}$. 
L'ensemble $\{1,\dots, {\mathsf{N}}\}$ sera par la suite noté $[{\mathsf{N}}]$.
Le $i^{\textrm{ème}}$ composant d'un élément 
$x \in \Bool^{\mathsf{N}}$ s'écrit  $x_i$.
Si l'ensemble $I$ est une partie de $[{\mathsf{N}}]$, alors 
$\overline{x}^I$ est l'élément $y\in  \Bool^{\mathsf{N}}$
tel que $y_i = 1 - x_i$ si $i\in I$ et  
$y_i = x_i$ sinon. 
On considère les deux abréviations $\overline{x}$ pour $\overline{x}^{[{\mathsf{N}}]}$ 
(chaque composant de $\overline{x}$ est nié:
c'est une négation composante à composante)
et $\overline{x}^i$ pour $\overline{x}^{\{i\}}$ pour $i \in [{\mathsf{N}}]$
(seul $x_i$ est nié dans $\overline{x}$).
Pour tout $x$ et  $y$ dans  $\Bool^{\mathsf{N}}$, l'ensemble 
$\Delta(x, y)$,  contient les $i \in [{\mathsf{N}}]$
tels que $x_i \neq y_i$.
Soit enfin $f : \Bool^n \rightarrow \Bool^{\mathsf{N}}$. Son $i^{\textrm{ème}}$ composant
est nommé $f_i$ qui est une fonction de $\Bool^{\mathsf{N}}$ dans $\Bool$.
Pour chaque 
$x$ dans $\Bool^{\mathsf{N}}$, l'ensemble 
$\Delta f(x)$ est défini par $\Delta f(x) = \Delta(x,f(x))$.
On peut admettre que $f (x) = \overline{x}^{\Delta f(x)}$ .

\begin{xpl}\label{xpl:1}
On considère ${\mathsf{N}}= 3$ et $f:\Bool^3 \rightarrow \Bool^3$ telle que
$f(x)=(f_1(x),f_2(x),f_3(x))$ avec  
$$\begin{array}{rcl}
f_1(x_1, x_2, x_3) &=& (\overline{x_1} + \overline{x_2}).x_3 \textrm{, }\\
f_2(x_1, x_2, x_3) &= &x_1.x_3 \textrm{ et }\\
f_3(x_1, x_2, x_3) &=& x_1 + x_2 + x_3.
\end{array}
$$

\begin{table}[ht]
$$
\begin{array}{|l|l|l||c|c|c|}
\hline
\multicolumn{3}{|c||}{x} & 
\multicolumn{3}{|c|}{f(x)} \\
\hline
x_1 & x_2 & x_3 & 
f_1(x) & f_2(x) & f_3(x) \\
\hline
0& 0 & 0 & 0 & 0  & 0 \\
\hline 
0& 0 & 1 & 1 &  0 & 1\\
\hline 
0& 1 & 0 & 0 & 0& 1\\
\hline 
0& 1 & 1 & 1 & 0& 1\\
\hline 
1& 0 & 0 & 0 & 0& 1\\
\hline 
1& 0 & 1 & 1 & 1& 1\\
\hline 
1& 1 & 0 & 0 & 0& 1\\
\hline 
1& 1 & 1 & 0 & 1& 1\\
\hline 
\end{array}
$$
\caption{Images de 
$(x_1, x_2, x_3) \mapsto 
((\overline{x_1} + \overline{x_2}).x_3,
x_1.x_3,
x_1 + x_2 + x_3)$ \label{table:xpl:images}}
\end{table}

La \textsc{Table}~\ref{table:xpl:images} donne l'image de chaque élément
$x \in \Bool^3$.
Pour $x=(0,1,0)$ les assertions suivantes se déduisent directement du tableau:
\begin{itemize}
\item $f(x)=(0,0,1)$;
\item pour $I=\{1,3\}$, $\overline{x}^{I} = (1,1,1)$ et 
  $\overline{x} = (1,0,1)$; 
\item $\Delta(x,f(x)) = \{2,3\}$.
\end{itemize}

\end{xpl}

\subsection{Réseau booléen}
Soit $n$ un entier naturel représentant le nombre 
d'éléments étudiés (gènes, protéines,\ldots).
Un réseau booléen  est 
défini à partir d'une fonction booléenne:
\[
f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}},\qquad x=(x_1,\dots,x_{\mathsf{N}})\mapsto f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x)),
\]
et un  {\emph{schéma itératif}} ou  encore \emph{mode de  mise à jour}. À  partir d'une configuration initiale $x^0\in\Bool^{\mathsf{N}}$,  la suite $(x^{t})^{t
  \in  \Nats}$ des  configurations  du  système est  construite  selon l'un  des
schémas suivants :
\begin{itemize}
\item \textbf{Schéma parallèle  synchrone :} basé sur la  relation de récurrence
  $x^{t+1}=f(x^t)$. Tous  les $x_i$, $1 \le  i \le {\mathsf{N}}$,  sont ainsi mis à  jour à
  chaque itération en utilisant l'état global précédent du système $x^t$.
\item \textbf{Schéma  unaire :} ce schéma  est parfois 
  qualifié de chaotique 
  dans  la littérature. 
  Il  consiste à modifier la valeur 
  d'un unique élément $i$,  $1 \le i \le  {\mathsf{N}}$, à
  chaque itération. Le choix de l'élément qui est modifié à chaque itération est
  défini  par une  suite 
  $S  = \left(s^t\right)^{t \in  \mathds{N}}$ qui est  une séquence
  d'indices dans $[{\mathsf{N}}]$. Cette suite est appelée \emph{stratégie unaire}. 
  Il est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par
  
\begin{equation}
  x^{t+1}_i=
  \left\{ \begin{array}{l}
      f_i(x^t) \textrm{ si } i=s^t, \\
      x^t_i\textrm{ sinon.}
    \end{array}
  \right.
\label{eq:schema:unaire}
\end{equation}



\item \textbf{Schéma généralisé:}  dans ce schéma, ce sont les valeurs  
  d'un ensemble d'éléments de $[{\mathsf{N}}]$ qui sont modifiées à  chaque  itération.
  Dans  le  cas  particulier où  c'est la valeur d'un  singleton
  $\{k\}$, $1 \le k  \le {\mathsf{N}}$, qui est modifiée à
  chaque  itération, on retrouve le
  mode unaire. Dans le second cas particulier où ce sont les valeurs de 
  tous les éléments de $\{1, \ldots,  {\mathsf{N}}\}$ qui sont  modifiées
  à chaque  itération, on retrouve  le mode
  parallèle.  Ce mode généralise donc les deux modes précédents.  
  Plus formellement,  à  la  $t^{\textrm{ème}}$
  itération, seuls les éléments de la partie 
  $s^{t} \in \mathcal{P}([{\mathsf{N}}])$ sont mis à
  jour.  La  suite $S  = \left(s^t\right)^{t \in  \mathds{N}}$ est  une séquence
  de sous-ensembles 
  de   $[{\mathsf{N}}]$   appelée   \emph{stratégie généralisée}.
  Il est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par
  \begin{equation}
  x^{t+1}_i=
  \left\{ \begin{array}{l}
      f_i(x^t) \textrm{ si } i \in s^t, \\
      x^t_i\textrm{ sinon.}
    \end{array}
  \right.
\label{eq:schema:generalise}
\end{equation}




  \end{itemize}


 
 

La section suivante détaille comment représenter graphiquement les évolutions de tels réseaux.
\subsection{Graphes des itérations}



Pour un entier naturel ${\mathsf{N}}$ et une 
fonction $f : B^{\mathsf{N}} \rightarrow B^{\mathsf{N}}$, plusieurs évolutions sont possibles
en fonction du schéma itératif retenu. 
Celles-ci sont représentées par un graphe orienté dont les noeuds 
sont les éléments de $\Bool^{\mathsf{N}}$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).


\begin{itemize}
\item Le \emph{graphe des itérations synchrones} de $f$, noté $\textsc{gis}(f)$ 
est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si 
et seulement si $y=f(x)$.
\item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{giu}(f)$
est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ pour $x \neq$ si 
et seulement s'il existe $i \in \Delta f(x)$ tel que $y = \overline{x}^i$.
Si $\Delta f(x)$ est vide, on ajoute l'arc $x \rightarrow x$.

\item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$
est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si 
et seulement s'il existe un ensemble $I\subseteq \Delta f(x)$ tel que 
$y = \overline{x}^I$. On peut remarquer que ce graphe contient comme 
sous-graphe à la fois celui des itérations synchrones et celui 
des itérations unaires.


\end{itemize}



\begin{xpl}
On reprend notre exemple illustratif
détaillé à la page~\pageref{xpl:1} avec sa table
d'images (\textsc{Table}~\ref{table:xpl:images}).
La \textsc{Figure}~\ref{fig:xpl:graphs} donne les trois graphes d'itérations 
associés à $f$.

\begin{figure}%[ht]
  \begin{center}
    \subfigure[$\textsc{gis}(f)$]{
      \begin{minipage}{0.33\textwidth}
        \begin{center}
          \includegraphics[scale=0.4]{fsig}
        \end{center}
      \end{minipage}
      \label{fig:fsig}
    }
    \subfigure[$\textsc{giu}(f)$]{
      \begin{minipage}{0.33\textwidth}
        \begin{center}
          \includegraphics[scale=0.4]{faig}
        \end{center}
      \end{minipage}
      \label{fig:faig}
    }   
    \subfigure[$\textsc{gig}(f)$]{
      \begin{minipage}{0.33\textwidth}
        \begin{center}
          \includegraphics[scale=0.4]{fgig}
        \end{center}
      \end{minipage}
      \label{fig:fgig}
    }
  \end{center}
  \caption{Graphes des itérations de la fonction 
$f:\Bool^3 \rightarrow \Bool^3$ telle que  
$(x_1, x_2, x_3) \mapsto 
((\overline{x_1} + \overline{x_2}).x_3,
x_1.x_3,
x_1 + x_2 + x_3)$.\label{fig:xpl:graphs}
On remarque le cycle $((101,111),(111,011),(011,101))$ 
 à la \textsc{Figure}~(\ref{fig:fsig}).}
\end{figure}
\end{xpl} 


\subsection{Attracteurs}

On dit que le point 
$x \in \Bool^{\mathsf{N}}$ est un \emph{point fixe} de $f$ si  $x = f (x)$.
Les points fixes sont particulièrement intéressants car ils correspondent 
aux états stables:
dans chaque graphe d'itérations, le point $x$ est un point fixe 
si et seulement si il est son seul successeur.



Soit un graphe d'itérations (synchrones, unaires ou généralisées)
de $f$. 
Les \emph{attracteurs}  de ce graphe sont les 
plus petits sous-ensembles (au sens de l'inclusion) non vides
$A \subseteq \Bool^{\mathsf{N}}$ tels que pour tout arc
$x \rightarrow y$, si $x$ est un élément de $A$, alors 
$y$ aussi.
Un attracteur qui contient au moins deux éléments  est dit \emph{cyclique}.
On en déduit qu'un attracteur cyclique ne contient pas de point fixe.
En d'autres termes, lorsqu'un système entre dans un attracteur cyclique, 
il ne peut pas atteindre un point fixe.


On a la proposition suivante:


\begin{theorem}\label{Prop:attracteur}
Le point $x$ est un point fixe si et seulement si 
$\{x\}$ est un attracteur du graphe d'itération (synchrone, unaire, généralisé).
En d'autres termes, les attracteurs non cycliques de celui-ci 
sont les points fixes de $f$.
Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin 
depuis $x$ qui atteint un attracteur.
Ainsi tout graphe d'itérations contient toujours au moins un attracteur.
\end{theorem}



\begin{xpl}
Les attracteurs de $\textsc{giu}(f)$ et de $\textsc{gig}(f)$ sont 
le point fixe $000$ et l'attracteur cyclique 
$\{001, 101,111, 011  \}$. 
Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$
et l'attracteur cyclique $\{011, 101, 111\}$.
\end{xpl}

\subsection{Graphe d'interaction}
Les interactions entre les composants du 
système peuvent être mémorisées 
dans la {\emph{matrice jacobienne discrète}} $f'$.
Celle-ci est définie comme étant la fonction  qui  à chaque 
configuration $x\in\Bool^{\mathsf{N}}$ associe la matrice de taille 
$n\times n$ telle que 
\begin{equation}
f'(x)=(f'_{ij}(x)),\qquad 
f'_{ij}(x)=\frac{f_i(\overline{x}^j){-}f_i(x)}{\overline{x_j}{-}x_j}\qquad (i,j\in[n]).
\label{eq:jacobienne}
\end{equation}
On note que dans l'équation donnant la valeur de $f'_{ij}(x)$, 
les termes $f_i(\overline{x}^j)$, $f_i(x)$, 
$\overline{x}^j_j$ et $x_j$ sont considérés comme des entiers naturels 
égaux à $0$ ou à $1$ et que la différence est effectuée
 dans $\Z$.
Lorsqu'on supprime les signes dans la matrice jacobienne discrète, 
on obtient une matrice notée $B(f)$ aussi de taille 
${\mathsf{N}}\times {\mathsf{N}}$.
Celle-ci mémorise uniquement 
l'existence d'une dépendance de tel élément vis à vis de 
 tel élément.
Elle ne mémorise pas \emph{comment} dépendent les éléments 
les uns par rapport aux autres. Cette matrice est nommée 
\emph{matrice d'incidence}.  

\begin{theorem}
Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$, 
$f_i(\overline{x}^j)$ est égal à  $f_i(x)$, \textit{i.e.}, 
$f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
\end{theorem} 




En outre, les interactions peuvent se  représenter à l'aide d'un 
graphe $\Gamma(f)$ orienté et signé défini ainsi: 
l'ensemble des sommet %s est 
$[{\mathsf{N}}]$ et il existe un arc de $j$ à $i$ de signe
 $s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
un $x\in\Bool^{\mathsf{N}}$. 

On note que la présence de 
deux arcs de signes opposés entre deux sommets donnés 
est possible.
% Dans la suite, le graphe signé $G$ sera qualifié de 
% \emph{simple} si, pour chaque  $i$, $j$ dans $[n]$,
% il existe au plus un arc de $j$ à $i$ dans $G$.
Un cycle \emph{positif} (resp. négatif) de $G$
est un cycle \emph{élémentaire} qui contient un nombre 
pair (resp. impair) d'arcs négatifs. 
La \emph{longueur}
d'un cycle est le nombre d'arcs qu'il contient.

\begin{xpl}
Pour exprimer la jacobienne discrète de la fonction donnée en exemple,
pour chaque $i$, $j$ dans
$[3]$ on exprime 
$f'_{ij}(x)=
\frac
{f_i(\overline{x}^j){-}f_i(x)}
{\overline{x_j}{-}x_j}$
d'après l'équation~(\ref{eq:jacobienne}).
% Ainsi 
% $$
% f'_{12} (x_1,x_2,x_3)=  
% \frac
% { ((\overline{x_1} + \overline{\overline{x_2}}).x_3)
% {-}  
% ((\overline{x_1} + \overline{x_2}).x_3) 
% }
% {\overline{x_2}{-}x_2} =  \frac{   
% ((\overline{x_1} + x_2).x_3)
% {-}  
% ((\overline{x_1} + \overline{x_2}).x_3) 
% }{\overline{x_2}{-}x_2} .
% $$
% Évaluons cette fonction de $\Bool^3$ dans $\Z$ en construisant le tableau de toutes ses valeurs.
% $$
% \begin{array}{|c|c|c|c|c|c|c|c|}
% \hline
% x_1 &   x_2 &  x_3 &  
% (\overline{x_1} + {x_2}).x_3 & (\overline{x_1} + \overline{x_2}).x_3 &   
% (\overline{x_1} + {x_2}).x_3 {-} (\overline{x_1} + \overline{x_2}).x_3 & \overline{x_2} {-} x_2  &  
% f'_{12} (x_1,x_2,x_3)\\
% \hline
% 0   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
% 0   &  0    &  1   &  1  & 1 & 0 & 1   & 0 \\\hline
% 0   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
% 0   &  1    &  1   &  1  & 1 & 0 & -1  & 0 \\\hline
% 1   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
% 1   &  0    &  1   &  0  & 1 & -1 & 1   & -1 \\\hline
% 1   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
% 1   &  1    &  1   &  1  & 0 & 1& -1  & -1 \\\hline
% \end{array}
% $$
% La seule valeur de $f'_{12}$ qui n'est pas nulle est -1, qui est négative.
% Le graphe d'interaction contiendra ainsi un arc négatif entre le n{\oe}ud 2 et le n{\oe}ud 1.
La \textsc{Figure}~(\ref{fig:f:jacobienne}) explicite la matrice jacobienne discrète de cette fonction.

Le graphe d'interaction de $f$ s'en déduit directement. Il est donné à la 
\textsc{Figure}~(\ref{fig:f:interaction}). 
Il possède 
un cycle négatif de longueur 1 et 
un cycle négatif de longueur 3. 
Concernant les cycles positifs, il en possède 
un de longueur 1, 
deux de longueur 2 
et un de longueur 3.

La matrice d'incidence peut se déduire de la matrice d'interaction en supprimant les signes ou bien 
en constatant que $f_1$ dépend des trois éléments $x_1$, $x_2$ et $x_3$ et donc que la première ligne de $B(f)$ 
est égale à $1~1~1$. De manière similaire,  $f_2$ (resp. $f_3$) dépend  de 
$x_1$ et  de $x_3$ 
(resp. dépend de $x_1$, $x_2$ et $x_3$).
Ainsi la seconde ligne (resp. la troisième ligne) de $B(f)$ est $1~0~1$ (resp. est $1~1~1$). 
La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complète. 

\begin{figure}%[ht]
  \begin{center}
     \subfigure[Matrice jacobienne]{
       \begin{minipage}{0.90\textwidth}
         \begin{center}
        $
        \left(
          \begin{array}{ccc}
            \frac{   
              ((x_1 + \overline{x_2}).x_3)
              {-}  
              ((\overline{x_1} + \overline{x_2}).x_3) 
            }{\overline{x_1}{-}x_1}
            &
            \frac{   
              ((\overline{x_1} + x_2).x_3)
              {-}  
              ((\overline{x_1} + \overline{x_2}).x_3) 
            }{\overline{x_2}{-}x_2}
            &
            \frac{   
              ((\overline{x_1} + \overline{x_2}).\overline{x_3})
              {-}  
              ((\overline{x_1} + \overline{x_2}).x_3) 
            }{\overline{x_3}{-}x_3} 
\\
\\
            \frac{\overline{x_1}.x_3 {-} x_1.x_3}{\overline{x_1}{-}x_1}
             & 0 & 
\frac{{x_1}.\overline{x_3} {-} x_1.x_3}{\overline{x_3}{-}x_3}
 \\
\\
            \frac{(\overline{x_1}+x_2+x_3){-}(x_1+x_2+x_3)}{\overline{x_1}{-}{x_1}} &
            \frac{(x_1+\overline{x_2}+x_3){-}(x_1+x_2+x_3)}{\overline{x_2}{-}{x_2}} &
            \frac{(x_1+x_2+\overline{x_3}){-}(x_1+x_2+x_3)}{\overline{x_3}{-}{x_3}} 
          \end{array}
        \right)
        $
         \end{center}
       \end{minipage}
       \label{fig:f:jacobienne}
     } 
    ~ 
    \subfigure[Graphe d'interaction]{
      \begin{minipage}{0.45\textwidth}
      \begin{center}
        \includegraphics[scale=0.5]{gf}
      \end{center}
      \label{fig:f:interaction}
    \end{minipage}
    }
    
    \subfigure[Matrice d'incidence]{
      \begin{minipage}{0.45\textwidth}
        \begin{center}
          $
          B(f) =
          \left(
            \begin{array}{ccc}
              1 & 1 & 1 \\
              1 & 0 & 1 \\
              1 & 1 & 1 
            \end{array}
          \right)
          $
        \end{center}
        \label{fig:f:incidence}
    \end{minipage}
  }
\end{center}  
\caption{Représentations des dépendances entre les éléments 
de la fonction 
$f:\Bool^3 \rightarrow \Bool^3$ telle que  
$(x_1, x_2, x_3) \mapsto 
((\overline{x_1} + \overline{x_2}).x_3,
x_1.x_3,
x_1 + x_2 + x_3)$}
\end{figure}
\end{xpl}




Soit $P$ une suite d'arcs de $\Gamma(f)$ de la forme
\[
(i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
\]
Alors, $P$ est dit un chemin de $\Gamma(f)$ de longueur $r$ et de signe
$\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
$i_1$. 
$P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
$i_1$,\ldots $i_r$ sont deux à deux disjoints.
Un sommet $i$ de $\Gamma(f)$ a une {\emph{boucle}} 
positive (resp. négative) , si $\Gamma(f)$ a un 
arc positif (resp. un arc négatif) de $i$ vers lui-même.



\subsection{Conditions de convergence}\label{sec:Robert:async}

Parmi les itérations unaires caractérisées par leurs stratégies
$S=(s^t)^{t \in \Nats}$ d'éléments appartenant à $[{\mathsf{N}}]$,
sont jugées intéressantes 
celles qui activent au moins une fois
chacun des $i\in[{\mathsf{N}}]$. Dans le cas contraire, un élément n'est jamais modifié. 

Plus formellement, une séquence finie $S=(s^t)^{t \in \Nats}$
est dite \emph{complète} relativement à $[{\mathsf{N}}]$ si 
tout indice de $[{\mathsf{N}}]$
s'y retrouve au moins une fois.

Parmi toutes les stratégies unaires de 
$[{\mathsf{N}}]^{\Nats}$, on qualifie de:
\begin{itemize}
\item \emph{périodiques} celles 
qui sont constituées par une répétition indéfinie 
d'une même séquence $S$ complète relativement à $[{\mathsf{N}}]$.
En particulier toute séquence périodique est complète.
\item \emph{pseudo-périodiques} celles 
qui sont constituées par une succession indéfinie de séquences 
(de longueur éventuellement variable non supposée bornée) complètes.
Autrement dit dans chaque stratégie pseudo-périodique, chaque indice de
$1$ à ${\mathsf{N}}$ revient indéfiniment.
\end{itemize}


François Robert~\cite{Rob95}
a énoncé en 1995 le théorème suivant de convergence 
dans le mode des itérations unaires.

\begin{theorem}\label{Th:conv:GIU}
Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie unaire est
pseudo-périodique, alors tout chemin de $\textsc{giu}(f)$ atteint 
l'unique point fixe $\zeta$ en au plus ${\mathsf{N}}$ pseudo-périodes.
\end{theorem}

Le qualificatif \emph{pseudo-périodique} peut aisément 
s'étendre aux stratégies généralisées comme suit.
Lorsqu'une stratégie généralisée est constituée d'une 
succession indéfinie de séquences de parties de $[{\mathsf{N}}]$ 
dont l'union est $[{\mathsf{N}}]$, cette stratégie est {pseudo-périodique}.
J. Bahi~\cite{Bah00} a démontré le théorème suivant:

\begin{theorem}\label{Th:Bahi}
Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie généralisée
est pseudo-périodique alors
tout chemin de $\textsc{gig}(f)$ (et donc de $\textsc{giu}(f)$) 
finit par atteindre
l'unique point fixe $\zeta$. 
\end{theorem}

% \section{Distance sur l'espace $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$}\label{sub:metric}
% On considère l'espace $\mathcal{X}=\llbracket 1;n\rrbracket^{\Nats}\times
% \Bool^n$ et
% on définit la distance $d$ entre les points $X=(s,x)$ et
% $X'=(s',x')$ de $\mathcal{X}$ par 
% \[
% d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
% \left\{
% \begin{array}{l}
% \displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] 
% \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
% \end{array}
% \right.\,.
% \]
% On note que dans le calcul de $d_H(x,x')$-- 
% appelée \gls{distanceHamming} (cf. glossaire) entre $x$ et $x'$-- 
% les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels 
% égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
% De plus, la \gls{partieentiere} (cf. glossaire) 
% $\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance 
% de Hamming entre $x$ et $x'$. 
% %D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$ 
% %mesure la différence entre $s$ et $s'$.
% On remarque que la partie décimale est inférieure à $10^{-l}$ si
% et seulement si les $l$ premiers termes des deux stratégies sont égaux. 
% De plus, si la 
% $(l+1)^{\textrm{ème}}$ décimale  
% de $d_S(s,s')$ 
% n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 

% On a  démontré que pour toute fonction booléenne $f$, 
% $G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).