\documentclass[12pt,a4paper,twoside]{article}

\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{aafrench}
\input{c:/tex/aaa/oi/exs/exs} %inclue ifthen
\usepackage{alltt}                          %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlg}    %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpic}  %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpicf} %DECOMMENTER CETTE LIGNE
%\newcommand{\FigMlPic}[3]{\mbox{}\\FIGURE\\} %COMMENTER CETTE LIGNE

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 %\maketitle
 \thispagestyle{empty}
  \sujet{Confluence (ENS Lyon, Maths-Info)}
  \texte
   On s'intéresse aux mots non vides constitués uniquement des lettres
   $B$ et $N$. On définit sur ces mots la relation
   $X\cc RY$ si et seulement si le mot $Y$ s'obtient en remplaçant
   dans le mot $X$ une séquence $BN$ par $N$, ou $NB$ par $N$,
   ou $BB$ par $B$, ou $NN$ par $B$
  \question
   Montrer que toute suite telle que $X_n\cc RX_{n+1}$ termine.
  \question
   Montrer que toutes les suites commençant par un même mot $X_0$
   terminent sur le même mot.
  \texte
   On se propose de généraliser ce résultat.
   $\rightarrow$ est une relation binaire sur un ensemble $\cc X$;
   on note $\xrightarrow{*}$ la fermeture réflexive et transitive
   de $\rightarrow$. On donne les définitions suivantes:
   \ev
   $\rightarrow$ \emph{termine} si il n'existe pas de suite
   $(x_n)_{n\geq0}$ telle que $\forall n\in\N,\,x_n\rightarrow x_{n+1}$.
   \ev
   $\rightarrow$ est \emph{localement confluente} si
   $$\forall x,y_1,y_2\in\cc X,\,(x\rightarrow y_1\text{ et }
    x\rightarrow y_2)\Rightarrow\exists z\in\cc X,\,y_1\xrightarrow{*}z
    \text{ et }y_2\xrightarrow{*}z\text{.}$$
   \ev
   $\rightarrow$ est \emph{globalement confluente} si
   $$\forall x,y_1,y_2\in\cc X,\,(x\xrightarrow{*}y_1\text{ et }
    x\xrightarrow{*}y_2)\Rightarrow\exists z\in\cc X,\,y_1\xrightarrow{*}z
    \text{ et }y_2\xrightarrow{*}z\text{.}$$   
  \question
   Montrer que si la relation $\rightarrow$ termine et est
   localement confluente, alors elle est globalement confluente.
  \question
   Montrer que la relation $\cc R$ est globalement confluente.
  \question
   Montrer que, sans la terminaison, la confluence locale n'implique
   pas la confluence globale.
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
  \cquestion
   La longueur du mot $X_n$ décroît strictement.
  \cquestion
   Si $G=\{b,n\}$ est le groupe à deux éléments ($b$ neutre, $nn=b$),
   soit $x$ l'élément de $G$ obtenu en remplaçant $B$ par $b$ et $N$ par
   $n$ dans le mot $X_0$. Si $x=b$ (resp. $n$), alors toute suite
   commençant par $X_0$ termine sur $B$ (resp. $N$).
  \cquestion
   Notons $P(x)$ la propriété
   $$\forall y_1,y_2\in\cc X,\,(x\xrightarrow{*}y_1\text{ et }
    x\xrightarrow{*}y_2)\Rightarrow\exists z\in\cc X,\,y_1\xrightarrow{*}z
    \text{ et }y_2\xrightarrow{*}z\text{.}$$
   Supposons que $P(y)$ soit vraie pour tous les $y$ tels que
   $x\xrightarrow{+}y$ et montrons $P(x)$ ($\xrightarrow{+}$ est
   la fermeture transitive de $\rightarrow$):
   Soient donc $y_1$ et $y_2$
   tels que $x\xrightarrow{*}y_1$ et $x\xrightarrow{*}y_2$.
   Si $y_1=x$ ou si $y_2=x$, l'existence de $z$ est immédiate.
   Sinon, il existe $y_1'$ et $y_2'$ tels que
   $x\rightarrow y_1'\xrightarrow{*}y_1$ et
   $x\rightarrow y_2'\xrightarrow{*}y_2$. Comme $\rightarrow$ est
   localement confluente, il existe
   $z'$ vérifiant
   $y_1'\xrightarrow{*}z'$ et $y_2'\xrightarrow{*}z'$.
   Par hypothèse, il existe alors $z''$ tel que
   $y_1\xrightarrow{*}z''$ et $z'\xrightarrow{*}z''$;
   puis $z$ tel que $z''\xrightarrow{*}z$ et $y_2\xrightarrow{*}z$.
   $P(x)$ est bien démontré.
   \begin{center}\MlPic{cl002-01}\end{center}
   \evp
   Ce résultat montre que $P(x)$ est vérifiée pour tout $x$ car s'il existe
   un $x_0$ ne vérifiant pas $P(x_0)$, on peut trouver un $x_1$
   ne vérifiant pas $P(x_1)$ et tel que $x_0\xrightarrow{+}x_1$
   puis un $x_2$
   ne vérifiant pas $P(x_2)$ et tel que $x_1\xrightarrow{+}x_2$
   et ainsi de suite; on contredit ainsi la terminaison.
  \cquestion
   Conséquence de la question 2.
  \cquestion
   Contre-exemple: $\cc X=\{y,z,x_0,x_1,x_2,\dotsc\}$,
   $x_0\rightarrow x_1\rightarrow x_2\rightarrow\dotsb$,
   $x_{2n}\rightarrow y$ et $x_{2n+1}\rightarrow z$.
\end{parenthese}\end{document}

