\documentstyle[12pt]{article}


\newcommand{\psib}{{\overline \psi}}

\newcommand{\eqi}{\sim_I}
\newcommand{\simi}{\equiv}

\newcommand{\f}{\forall}
\newcommand{\e}{\exists}
\newcommand{\sub}{\subseteq}

\newcommand{\Lra}{\Longrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}
\newcommand{\lra}{\longrightarrow}

\newcommand{\rg}[1]{{\rm rang}(#1)}

\newcommand{\lu}{|u|}
\newcommand{\lua}{|u|_a}
\newcommand{\lub}{|u|_b}
\newcommand{\luc}{|u|_c}
\newcommand{\lv}{|v|}
\newcommand{\lva}{|v|_a}
\newcommand{\lvb}{|v|_b}
\newcommand{\lvc}{|v|_c}
\newcommand{\lw}{|w|}
\newcommand{\lwa}{|w|_a}
\newcommand{\lwb}{|w|_b}
\newcommand{\lwc}{|w|_c}
\newcommand{\lzb}{|z|_b}

\newcommand{\fnl}{{\it fnl}}
\newcommand{\fnf}{{\it fnf}}

\newcommand{\FNL}{{\rm FNL}}

\newcommand{\lon}[1]{|#1|}
\newcommand{\lona}[1]{|#1|_a}
\newcommand{\al}[1]{{\rm alph}(#1)}
\newcommand{\mini}[1]{{\rm min}(#1)}
\newcommand{\pro}[1]{\Pi_{\{a,b\}}(#1)}
\newcommand{\lin}[1]{{\rm lin}(#1)}
\newcommand{\Has}[1]{{\rm Hasse}(#1)}
\def\math#1{\ifmmode #1\else \mbox{$#1$}\fi}


\newcommand\Gr{\math{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm G$}
\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm G$}
\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm G$}
\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm G$} \hbox{\hbox to0pt{\kern0.4\wd0\vrule
height0.9\ht0\hss}\box0}} }}} 

\newcommand\Fr{\math{{\mathchoice {\hbox{$\textstyle\rm I\kern-0.2em F$}}
{\hbox{$\textstyle\rm I\kern-0.2em F$}} {\hbox{$\scriptstyle\rm I\kern-0.15em F$}}
{\hbox{$\scriptscriptstyle\rm I\kern-0.1em F$}} }}} 

\newcommand\Mr{\math{{\mathchoice {\hbox{$\textstyle\rm I\kern-0.2em M$}}
{\hbox{$\textstyle\rm I\kern-0.2em M$}} {\hbox{$\scriptstyle\rm I\kern-0.15em M$}}
{\hbox{$\scriptscriptstyle\rm I\kern-0.1em M$}} }}} 

\newcommand\N{\math{{\mathchoice {\hbox{$\textstyle\rm I\kern-0.2em N$}}
{\hbox{$\textstyle\rm I\kern-0.2em N$}} {\hbox{$\scriptstyle\rm I\kern-0.15em N$}}
{\hbox{$\scriptscriptstyle\rm I\kern-0.1em N$}} }}} 

\newcommand\G{\Gr(A,I)}
\newcommand\M{\Mr(A,I)}
\newcommand\F{\Fr(A,I)}

\newcommand\rec{{\rm Rec}(\Mr(A,I))}
\newcommand\crat{{\rm c\!-\!Rat}(\Mr(A,I))} 

\newcommand\reca{{\rm Rec}(A^*)}
\newcommand\rata{{\rm Rat}(A^*)} 


\input{accent_keys}

\begin{document}

\begin{sloppy}

\begin{center}
{\Large \bf Corrig\'e}
\vspace{0.5cm}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Combinatoire}
\begin{enumerate} 
\item Par transitivit\'e, il suffit de montrer les propri\'et\'es pour deux mots $u,v$
tels que $(u,v) \in R$. C'est alors imm\'ediat.  
\item 
\begin{itemize}  
\item Il est imm\'ediat de montrer que la condition est n\'ecessaire pour deux mots $u,v$ tels
que $(u,v) \in R$. A nouveau, par transitivit\'e, la condition est n\'ecessaire dans le cas
g\'en\'eral.
\item Montrons la condition suffisante par r\'ecurrence sur $\lu$. Notons que $\lua = \lva$ pour
tout $a \in A$ car $(a,a) \in D$, de l\`a $\lu = \lv$. Si $\lu = 0$, le r\'esultat est trivial.
Sinon, posons $u = cu'$, comme $\lvc = \luc$, $v=wcw'$ avec $\lwc = 0$. On a
$(c,w) \in I$ sinon il existe $d \in \al{w}$ tel que $(c,d) \in D$, mais alors
$\Pi_{\{c,d\}}(u)$ commence par $c$ alors que $\Pi_{\{c,d\}}(v)$ commence par $d$
contrairement \`a l'hypoth\`ese $\Pi_{\{c,d\}}(u) = \Pi_{\{c,d\}}(v)$. Il est alors facile de
v\'erifier que $\pro{u'} = \pro{ww'}$ pour tout  couple $(a,b) \in D$. En appliquant
l'hypoth\`ese de r\'ecurrence, on a  $u' \eqi ww'$ et donc $u = au' \eqi aww' \eqi waw' =v$ (en
utilisant une fois encore $(a,w) \in I$).
\end{itemize}  
\item Pour chaque mot, on calcule ses projections sur tout ensemble $\{a,b\}$ avec $(a,b)
\in D$ ce qui se fait en temps lin\'eaire. On compare ensuite les projections des deux mots ce
qui est encore lin\'eaire.
\item Imm\'ediat en utilisant la question 1.2 et la simplifiabilit\'e dans $A^*$.
\item La condition est clairement n\'ecessaire. R\'eciproquement, soit $a$ tel que
$\Pi_{\{a,b\}}$ commence par $a$. Ainsi $u=u'au''$ avec $\lona{u'} = 0$. Soit $b \in
\al{u'}$, $(a,b) \in I$ sinon $\pro{u}$ commencerait par $b$.
\item Soit $u$ un mot. Soit $v$ un mot \'equivalent \`a $u$ et $a$ la premi\`ere lettre de $v$.
D'apr\`es les questions 1.2 et 1.5, $a \in \mini{u}$. Ainsi, $u = u'au''$ avec $(a,u') \in I$
et $v = av'$. De plus, en utilisant 1.4, on a que $v'$ et $u'u''$ sont \'equivalents.  On
en d\'eduit alors facilement l'algorithme (r\'ecursif) recherch\'e. Comme \'etape pr\'eliminaire,
on calcule $\pro{u}$ pour tout $(a,b) \in D$. On cr\'ee ensuite une proc\'edure r\'ecursive ayant
comme argument d'appel $(\pro{u})_{(a,b) \in D}$ et qui :

choisit une lettre minimale $c$ en utilisant la caract\'erisation de 1.5. On a alors
$u = u'cu''$ avec $(c,u') \in I$.

calcule les $\pro{u'u''}$ pour tout $(a,b) \in D$ (il suffit pour cela de supprimer
la premi\`ere occurrence de $c$ dans toutes les projections $\pro{u}$ o\`u elle appara\^{\i}t) 

s'appelle  avec comme nouvel argument $(\pro{u'u''})_{(a,b) \in D}$

Cette proc\'edure s'arr\^ete d\`es que son argument est constitu\'e d'un uplet de mots vides.\\ 
Le pire des cas est celui o\`u les lettres de $A$ sont deux \`a deux ind\'ependantes, la complexit\'e
est alors de l'ordre de $\lon{A}^n$ o\`u $n$ est la  longueur du mot.
\end{enumerate} 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Formes normales}
\begin{enumerate} 
\item Montrons que $u=av$ est sous \fnl\ ssi $a$ est la plus petite des lettres de
$\mini{u}$ et $v$ est sous \fnl. La condition est clairement n\'ecessaire. R\'eciproquement soit
$u'= bu'' \eqi u$ avec $b \in A$. D'apr\`es 1.1, $u = vbv'$ avec $\lvb = 0$, de plus d'apr\`es
1.2, $(v,b) \in I$ ainsi $b \in \mini{u}$ et de l\`a $a \leq b$. Si $a  < b$, on a $u < u'$.
Si $a=b$, $v \eqi u''$ d'apr\`es 1.4 et donc $v \leq u''$ puisque $v$ est sous
\fnl; ainsi $u=av \leq u'=au''$.

Soit $u$ un mot. On calcule d'abord, en temps lin\'eaire, $\pro{u}$ pour tout $(a,b) \in D$.
On d\'etermine ensuite la plus petite lettre de $\mini{u}$ en utilisant 1.5 et on recommence
en ne tenant plus compte de cette lettre.

\item Soit $A = \{a,b\}$ avec $a < b$ et $(a,b) \in I$. Le mot $aab$ est sous \fnl\ mais
pas sous \fnf. Le mot \'equivalent $aba$ est sous \fnf\ mais pas sous \fnl.

\item Soit $u$ un mot non vide. On montre l'existence d'un mot \'equivalent sous \fnf\ par
r\'ecurrence sur $\lu$. Si $\lu = 1$, le r\'esultat est trivial. Supposons maintenant
$u=u'a$, par hypoth\`ese de r\'ecurrence il existe un mot $v'=v_1\ldots v_k$ sous \fnf\ et
\'equivalent \`a $u'$. Si $(v_k,a) \not \in I$, il est imm\'ediat de v\'erifier que $v'a$
est sous \fnf. Sinon, soit $1 \leq i \leq k$ le plus petit entier tel que
$(v_i \ldots v_k,a) \in I$. Soit $v'_i$ le mot sous \fnl\ \'equivalent \`a $v_ia$. Alors
il est imm\'ediat de v\'erifier que le mot $v_1\ldots v_{i-1}v'_iv_{i+1} \ldots v_k$ est 
\'equivalent \`a $u$ et sous \fnf.

L'unicit\'e se d\'emontre par contradiction. Soit $u=u_1 \ldots u_n$ sous \fnf\ un mot de
longueur minimale parmi ceux ayant au moins un mot \'equivalent $v = v_1 \ldots v_k$ distinct
sous \fnf. On a $u_1 \neq v_1$ (sinon, en utilisant 1.4, on contredirait la
minimalit\'e de $u$). Comme $u_1$ et $v_1$ sont tous les deux sous fnl (condition F2), on
en d\'eduit que $\al{u_1} \neq \al{v_1}$. Par sym\'etrie, on peut donc supposer qu'il
existe une lettre $b \in \al{v_1} \setminus \al{u_1}$. D'apr\`es 1.1, $b \in \al{u}$, d'o\`u
$u_2 \ldots u_n$ = $zbz'$ avec $\lzb = 0$. Mais alors d'apr\`es 1.2, $(u_1z,b) \in I$ ce qui
contredit la condition F3!

\item Montrons que $u$ est sous \fnf\ ssi $u=vw$ avec $v$ est le plus petit mot contenant
exactement une occurrence de chaque lettre de $\mini{u}$ et $w$ est sous \fnf. 

Si $u=u_1 \ldots u_n$ est sous \fnf, toutes les lettres de $u_1$ sont dans $\mini{u}$
d'apr\`es la condition F1 et ce sont les seules d'apr\`es la condition F3. Ainsi la condition
propos\'ee est n\'ecessaire (en posant $v=u_1$ et $w=u_2 \ldots u_n$). 

R\'eciproquement soit $(w_2, \ldots ,w_n)$ une d\'ecomposition de Foata de $w$. Alors
$(v,w_2, \ldots ,w_n)$ est une d\'ecomposition de Foata de $u$. En effet les conditions F0 et
F2 sont satisfaites par construction. Soient $a,b \in \mini{u}$ tels que $a$ pr\'ec\`ede $b$ dans
$u$, alors $u=u'au''br$ avec $(u'au'',b) \in I$. Ainsi $(a,b) \in I$
et la condition F1 est v\'erifi\'ee. Enfin, soit $a$ une lettre de $w_2$, comme $a$ n'est pas
minimale dans $u$, la condition F3 est v\'erifi\'ee.

On en d\'eduit l'algorithme de calcul de la \fnf\ suivant. Soit $u$ un mot. On calcule d'abord,
en temps lin\'eaire, $\pro{u}$ pour tout $(a,b) \in D$. On d\'etermine ensuite $\mini{u}$ en
utilisant 1.5 et on recommence en ne tenant plus compte de ces lettres.
\end{enumerate} 



\section{Reconnaissables}
\begin{enumerate} 
\item Il s'agit presque d'une ``question de cours''! \\
(i) $\Lra$ (ii): si $\eta$ reconna\^{\i}t $T \sub \M$, $\eta \circ \varphi$ reconna\^{\i}t
$\varphi^{-1}(T)$.\\
(ii) $\Lra$ (iii): soit $\eta: A^* \lra S$ reconnaissant $\varphi^{-1}(T)$ : il existe
$F \subseteq S$ tel que $\varphi^{-1}(T) = \eta^{-1}(F)$. Pour $u \in \M$, posons 
$S_u = \{ s \in S \mid \e x \in A^* \mbox{\rm\ tel que } \varphi(x) = u, \eta(x)s \in F\}$.
Il est alors facile de v\'erifier que $u^{-1}T = \bigcup_{s \in S_u}\varphi(\eta^{-1}(s))$.
L'ensemble $S$ \'etant fini, il existe un nombre fini de $S_u$ et donc de $u^{-1}T$.\\
(iii) $\Lra$ (i): Soit $K = \{ u^{-1}T \mid u \in \M\}$. L'ensemble fini $S$ des
applications de $K$ dans $K$ muni de la loi de composition interne d\'efinie par
$s \cdot s' = s' \circ s$ a une structure de mono\"{\i}de. Soit $\eta: \M \lra S$ d\'efini par
$\eta(v)(u^{-1}T) = v^{-1}(u^{-1}T) = (uv)^{-1}T$. Il est imm\'ediat de v\'erifier que $\eta$
est un morphisme et que 
$T = \eta^{-1}(\{ f \in S \mid \varepsilon \in f(\varepsilon^{-1}T) \})$ est reconnu par
$\eta$.
\item Soit $T \sub \M$ un langage de traces reconnu par un morphisme
$\eta$ de $\M$ dans un mono\"{\i}de fini $S$. L'ensemble $S \times {\cal P}(A)$ peut \^etre
muni d'une structure de mono\"{\i}de (produit) d'\'el\'ement neutre $(1_S,\emptyset)$
en posant $(s,B)(s',B') = (ss',B \cup B')$. Le langage $T$ est
clairement reconnu par le morphisme alphab\'etique $\eta'$ de $\M$ dans $S \times {\cal P}(A)$
d\'efini par $\eta'(t) = (\eta(t),\al{t})$.
\item D'apr\`es la question pr\'ec\'edente, on peut supposer que $T = \eta^{-1}(F)$ o\`u 
$\eta$ est un morphisme alphab\'etique de $\M$ dans un mono\"{\i}de fini $S$ et $F \sub S$. Pour
tout \'el\'ement  
$s$ de $\eta(\M)$, on peut d\'efinir sans ambiguit\'e $\al{s}$. Posons alors
$F' = \{ s \in \eta(\M) \mid \e s' \in \eta(\M), ss' \in F, \al{s} \mbox{\rm\ connexe et }
(\al{s},\al{s'}) \in I \}$. Il est alors facile de v\'erifier que
$c(T) = \eta^{-1}(F')$.
\item Soit $w \in A^*$. Montrons que $w \in \FNL$ ssi $(\dag) : $pour toute factorisation
$w =  xbyaz$ avec $(a,b) \in I$ et $a < b$, on a $(y,a) \not \in I$.

Si $w \in \FNL$, la condition $(\dag)$ est n\'ecessaire sinon $xabyz \sim xbyaz$ et $xabyz <
xbyaz$. R\'eciproquement, soit $w$ v\'erifiant la condition. Si $w \not \in \FNL$, il existe
$w' < w, w' \sim w$. Posons $w = ubv$, $w' = uav'$ avec $a < b$. Comme $w \sim w'$, on 
d\'eduit de 1.2 que $(a,b) \in I$. De $\lona{w}=\lona{w'}$, il vient $w = ubv'av''$ avec
$\lona{v'}=0$. En appliquant encore 1.2, on obtient $(v',a) \in I$ et contrairement \`a
l'hypoth\`ese la condition $(\dag)$ n'est pas v\'erifi\'ee.

Cette caract\'erisation de $\FNL$ montre que
$\FNL = A^* \setminus \bigcup_{(a,b) \in I, a<b}A^*bI(a)^*aA^*$ o\`u
$I(a) = \{b \in A \mid (a,b) \in I\}$. En utilisant le fait que tout langage rationnel de
mots est reconnaissable (th\'eor\`eme de Kleene) et que les langages reconnaissables sont clos
par compl\'ementaire, on en d\'eduit que $\FNL$ est reconnaissable.
\item Supposons $w$ non connexe. Alors 
$w = u_1v_1 \ldots   u_nv_nu_{n+1}$ avec $(u=u_1 \ldots   u_nu_{n+1},v=v_1 \ldots   v_n) \in I$ et
$u_i \neq   1, v_i \neq   1$ pour tout $1 \leq i \leq n$. Soit $a_i$ (resp. $b_i$) la premi\`ere
lettre de $u_i=a_iu'_i$ (resp. $v_i=b_iv'_i$) pour $1 \leq i \leq n$.
Comme $(u,v) \in I$ et $w \in \FNL$, on a $a_1 < b_1 < a_2 \ldots$.

Ou bien $u_{n+1} = 1$ auquel cas $w^2$ n'est pas dans $\FNL$ puisque 
$w^2 = u_1 \ldots u_n b_n v'_n a_1 u'_1 \ldots$ et $b_n v'_n a_1 \sim 	a_1 b_n v'_n$ et
$b_n v'_n a_1 > 	a_1 b_n v'_n$.

Ou bien $u_{n+1} = a_{n+1}u'_{n+1}$ avec $a_{n+1} \in A$. Comme pr\'ec\'edemment, on a alors
$b_n < a_{n+1}$. Ainsi $w^2$ n'est pas dans $\FNL$ puisque 
$w^2 = u_1 \ldots a_{n+1}u'_{n+1} u_1 b_1 v'_1 \ldots$ et 
$a_{n+1}u'_{n+1} u_1 b_1 \sim 	b_1 a_{n+1}u'_{n+1}u_1$ et
$a_{n+1}u'_{n+1} u_1 b_1 > 	b_1 a_{n+1}u'_{n+1}u_1$. 
\item Soit $T \in \rec$. D'apr\`es 3.1, $\varphi^{-1}(T) \in \reca$. Les langages
reconnaissables sont clos par intersection et donc, en utilisant 3.4,
$L= \varphi^{-1}(T) \cap \FNL \in \reca$. De plus on a clairement $\varphi(L) = T$.
D'apr\`es le th\'eor\`eme de Kleene, $L \in \rata$. Par d\'efinition, $L$ s'\'ecrit donc
\`a partir des langages finis en utilisant les op\'erations d'union, concat\'enation et
it\'eration. Par ailleurs, si $K$ et $K'$ sont deux langages de $A^*$, on a $\varphi(KL) =
\varphi(K)\varphi(L)$, $\varphi(K \cup L) = \varphi(K) \cup \varphi(L)$ et $\varphi(K^*) =
\varphi(K)^*$. Ainsi $T = \varphi(L)$ s'\'ecrit aussi \`a partir de langages finis de traces
en utilisant des op\'erations d'union, concat\'enation et it\'eration. Il suffit donc de montrer
que ces op\'erations d'it\'eration sont en fait des op\'erations de $c$-it\'eration. Supposons
donc que $L=L_1L_2^*L_3$. Tout mot de $L_2$ est alors connexe d'apr\`es 3.5 et donc
$T = \varphi(L) = \varphi(L_1)\varphi(L_2)^*\varphi(L_3)=
\varphi(L_1)\varphi(L_2)^{c-*}\varphi(L_3)$. Dans ce cas particulier, toute op\'eration
d'it\'eration peut donc \^etre remplac\'ee par une op\'eration de $c$-it\'eration et le langage
$T$ est bien dans $\crat$.
\end{enumerate} 


\section{Rang}
\begin{enumerate} 
\item L'implication (ii) entra\^{\i}ne (i) est imm\'ediate. R\'eciproquement montrons d'abord le
r\'esultat pour $n=1$ par r\'ecurrence sur $|x|$. 

Si $|x| = 0$, la propri\'et\'e est vraie en  posant $x_0=x_1=\varepsilon, y_0=u_0,
y_1=u_1$. Sinon posons
$x=ax'$ avec $a \in A$. 
\begin{itemize}   
\item Si $|u_0|_a = 0$, d'apr\`es 1.2, $(a,u_0) \in I$ et $u_1 \sim au'_1$.  Ainsi $ax'y \sim
u_0au'_1 \sim au_0u'_1$ et par 1.4, $x'y \sim u_0u'_1$. On peut alors appliquer l'hypoth\`ese
de r\'ecurrence : il existe $x'_0,x'_1,y'_0,y'_1$ telles que
$x' \sim x'_0x'_1, y \sim y'_0y'_1, u_0 \sim x'_0y'_0, u'_1 \sim x'_1y'_1$ et $(y'_0,x'_1)
\in I$. Posons  $x_0 = x'_0$, $x_1=ax'_1$, $y_0=y'_0$ et $y_1=y'_1$, comme $(a,u_0) \in I$,
on a en particulier $(a,x'_0) \in I$ et $(a,y'_0) \in I$. Ainsi $x = ax' \sim ax'_0x'_1 \sim
x'_0ax'_1 \sim x_0x_1$ et le r\'esultat est obtenu dans ce cas.
\item Si $|u_0|_a > 0$, $u_0 \sim au'_0$. On applique l'hypoth\`ese de r\'ecurrence \`a
$x'y \sim u'_0u_1$ : il existe $x'_0,x'_1,y'_0,y'_1$ telles que
$x' \sim x'_0x'_1, y \sim y'_0y'_1, u'_0 \sim x'_0y'_0, u_1 \sim x'_1y'_1$ et $(y'_0,x'_1)
\in I$. La formule cherch\'ee est obtenue en posant  $u_0 = au'_0$.
\end{itemize}  Le r\'esultat pour une valeur quelconque de $n$ s'obtient par une r\'ecurrence
facile. 

\item Soient $x,y \in A^*$, $x \sim a^pb^q, y \sim a^rb^s$. Ainsi $\rg{x,y,a^*b^*} = 1$.
Par contre, il est facile de v\'erifier que $\rg{a^n,b^n,(ab)^*} = n-1$ et donc
$\rg{L} = \omega$.
\item Soient $x,y \in A^*$ tels qu'il existe $x_1 \in L_1,x_2 \in L_2$ avec  
$xy \sim x_1x_2$. D'apr\`es la question 4.1, il existe $p,q,r,s$ avec
$x \sim pq$, $y \sim rs$, $x_1 \sim pr$, $x_2 \sim qs$ et $(q,r) \in I$. 
Comme $L_1$ est clos, on a $pr \in L_1$ et de m\^eme $qs \in L_2$. Ainsi $pqrs
\in L_1L_2$ et $\rg{x,y,L_1L_2} \leq 1$.
\item Soit $x,y \in A^*$ tels que $xy$ soit \'equivalent \`a un mot de $L^*$. D'apr\`es 4.1 et en
utilisant le fait que $L$ est clos, il existe $x_1,\ldots,x_n,y_1,\ldots,y_n \in A^*$ tels
que
$x \sim x_1 \ldots   x_n, y \sim y_1 \ldots   y_n$, $x_iy_i \in L$ pour $1 \leq i \leq n$ et
$(y_i,x_{i+1} \ldots x_n) \in I$ pour $1 \leq i < n$. Soit $i$ tel que $x_i \neq   1$, $y_i
\neq   1$.  Comme $x_iy_i$ est connexe, il existe $a_i \in \al{x_i}, b_i \in \al{y_i}$ tel
que
$(a_i,b_i) \in D$. Comme $(b_i,x_{i+1} \ldots x_n) \in I$, les lettres $b_i$ sont deux \`a
deux distinctes. Ainsi il existe au plus $k \leq |A|$ indices $i$ tels que $x_i \neq   1$ et
$y_i
\neq   1$. En regroupant les facteurs pour lesquels $x_i = 1$ ou $y_i = 1$ par blocs (chacun
de ces blocs est dans $L^*$), on obtient
$x \sim w_0x_1w_1 \ldots   x_kw_k, y \sim z_0y_1z_1 \ldots   y_kz_k$, 
$x_iy_i \in L$ pour $1 \leq i \leq k$, $w_i, z_i \in L^*$ pour $0 \leq i \leq k$, 
$(y_i,w_{i+1} \ldots x_kw_k) \in I$ pour $1 \leq i < k$ et
$(z_i,x_{i+1}w_{i+1} \ldots x_kw_k) \in I$ pour $1 \leq i < k$. Comme
$w_0z_0 (x_1y_1) \ldots w_1z_1 \ldots (x_ky_k) w_k z_k \in L^*$, on obtient le r\'esultat
cherch\'e.
\item Soit $k = \rg{L}$ et $T = \varphi(L)$. Soit $\eta$ un morphisme (que l'on supposera
alphab\'etique gr\^ace \`a la question 3.2 appliqu\'ee \`a $\Mr(A^*,\emptyset)$) de $A^*$ dans un
mono\"{\i}de fini $S$ reconnaissant $L$. Pour tout $u \in \M$, posons
$R(u) = \{ (s_0,\ldots,s_k) \mid \e x_0,\ldots x_k \in A^* \mbox{\rm\ tels que }
u = \varphi(x_0 \ldots x_k) \mbox{\rm\ et } s_i = \eta(x_i) \mbox{\rm\ pour tout }
0 \leq i \leq k \}$.

Montrons que si $u$ et $u'$ sont deux traces telles que $R(u) = R(u')$ alors
$u^{-1}T = u'^{-1}T$. Le nombre de $R(u)$ distincts \'etant major\'e par $2^{|S|^{k+1}}$, on en
d\'eduira que $T$ est reconnaissable gr\^ace \`a 3.1. 

Soit $v \in u^{-1}T$ et $x,y \in A^*$ avec $u= \varphi(x), v = \varphi(y)$. 
Le mot $xy$ est \'equivalent \`a un mot de $L$, ainsi comme $\rg{L} = k$, il existe
$x_0,y_0,\ldots,x_k,y_k \in A^*$ tels que
$x \sim x_0 \ldots   x_k, y \sim y_0 \ldots   y_k$, $x_0y_0 \ldots x_ky_k \in L$ et
$(y_i,x_{i+1} \ldots x_n) \in I$ pour $0 \leq i < n$. On a donc
$(\eta(x_0),\ldots,\eta(x_n)) \in R(u)$, comme $R(u) =R(u')$ il existe des mots
$x'_0,\ldots,x'_k \in A^*$ tels que $u' = \varphi(x'_0 \ldots x'_k)$ et
$\eta(x'_i) = \eta(x_i)$ pour tout $0 \leq i \leq k$. Le morphisme $\eta$ \'etant
alphab\'etique, on a en particulier $\al{x'_i} = \al{x_i}$ pour tout $0 \leq i \leq k$.
Par ailleurs le morphisme $\eta$ reconna\^{\i}t $L$ et comme 
$\eta(x_0y_0 \ldots x_ky_k) = \eta(x'_0y_0 \ldots x'_ky_k)$, on en d\'eduit 
$x'_0y_0 \ldots x'_ky_k \in L$. Finalement $(x'_0 \ldots x'_k)(y_0 \ldots y_k)$ est
\'equivalent \`a un mot de $L$ et donc $u'v \in T$. Ainsi $u^{-1}T \sub u'^{-1}T$ et par
sym\'etrie $u^{-1}T = u'^{-1}T$. 

\item Consid\'erons $A = \{a,b\}$ avec $(a,b) \in I$ et $L = (ab)^* (a^* \cup b^*)$.
Alors $\varphi(L) = \M$ est reconnaissable alors que le rang de $L$ n'est pas fini
(par exemple $\rg{a^n,b^n,L} = n-1$ pour tout $n$).
\item $\rec$ contient clairement l'ensemble vide et les langages $\{\varphi(a)\}$
pour $a \in A$. Si $u \in \M$ et $T_1, T_2 \sub \M$, on a
$u^{-1}(T_1 \cup T_2) = u^{-1}T_1 \cup u^{-1}T_2$, de l\`a $\rec$ est clos par union
(en utilisant 4.1). $\rec$ est clos par concat\'enation d'apr\`es 4.3 et 4.5 et $\rec$
est clos par it\'eration concurrente d'apr\`es 3.3, 4.4 et 4.5. Ainsi par d\'efinition de 
$\crat$, $\crat \sub \rec$. 
\end{enumerate} 

\section{Graphes de d\'ependances}
\begin{enumerate} 
\item Pour $a \in A$, soit $f_a$ le graphe de d\'ependance constitu\'e d'un seul sommet
$(a,0)$ et sans ar\^ete. Soit $\psi$ le morphisme de $A^*$ dans \F\ qui envoie toute lettre
$a \in A$ sur $f_a$. Par d\'efinition de la concat\'enation dans \F, il est clair que
$f_a \cdot f_b = f_b \cdot f_a$ d\`es que $(a,b) \in I$. Ainsi $\psi$ se factorise en un
morphisme $\psib$ de \M\ dans \F. Soit $u \in A^*$ et $t = \varphi(u) \in \M$, il est imm\'ediat
de v\'erifier que $\psib(t) = ((\lona{t})_{a \in A},E)$ avec $((a,i),(b,j)) \in E$ si et
seulement si $(a,b) \in D$ et dans le mot $\Pi_{\{a,b\}}(u)$ (qui ne d\'epend que de $t$
d'apr\`es la question 1.2) la $i^{\grave{e}me}$ occurrence de $a$ est avant la 
$j^{\grave{e}me}$ occurrence de $b$.

Montrons que $\psib$ est une bijection. Soit $f = (V_f,E_f) \in \F$ et soit 
$(a_1,i_1) \ldots (a_n,i_n)$ une \'enum\'eration de $V_f$ compatible avec $E_f$
(i.e. telle que $((a_j,i_j),(a_k,i_k)) \in E_f$ entra\^{\i}ne $j < k$). Il est facile de
v\'erifier que $\psi(a_1 \ldots a_n) = f$. Ainsi $\psib$ est surjective. Soient
$u,v \in \M$ avec $\psib(u) = \psib(v) = ((n_a)_{a \in A},E_f)$. Soit $(a,b) \in D$, posons
$V_{a,b} = V_a(n_a) \cup V_b(n_b)$. Par d\'efinition d'un graphe de d\'ependance, les \'el\'ements
de $V_{a,b}$ sont totalement ordonn\'es et d\'efinissent donc un mot $x \in \{a,b\}^*$. D'apr\`es
la caract\'erisation de $\psi$ donn\'ee ci-dessus, on a $x = \pro{u}$. Ainsi 
$\pro{u} = \pro{v}$ et par la question 1.2, $u=v$ et $\psib$ est injective.
\item Tout ensemble admettant une borne sup\'erieure est \'evidemment coh\'erent. R\'eciproquement
soit $K \subseteq \G$ coh\'erent. D\'efinissons $V = \bigcup_{g \in K}V_g$ et 
$E = \bigcup_{g \in K}E_g$ et montrons que $(V,E)$ est un graphe de d\'ependance et que c'est
la borne sup\'erieure de $K$. 

C1: Supposons que  $(a,i), (b,j) \in V$ avec $((a,i),(b,j)) \in E^+$ et $((b,j),(a,i)) \in
E^+$. Il existe $f,g \in K$ tels que $(a,i) \in V_f$ et $(b,j) \in V_g$. Comme $K$ est
coh\'erent, il existe $h \in \G$ tel que $f \leq h$ et $g \leq h$. Ainsi $(a,i), (b,j) \in
V_h$ et il est facile de v\'erifier que  $((a,i),(b,j)) \in E_h^+$ et $((b,j),(a,i)) \in E_h^+$
contrairement \`a l'hypoth\`ese que $h$ v\'erifie C2.

C2: Si $((a,i),(b,j)) \in E$, il existe $g \in K$ tel que $((a,i),(b,j)) \in E_g$ et donc
$(a,b) \in D$. R\'eciproquement soient $(a,i) \neq (b,j) \in V$ avec $(a,b) \in D$. Il
existe $f,g \in K$ tels que $(a,i) \in V_f$ et $(b,j) \in V_g$. Comme $K$ est coh\'erent, il
existe $h \in \G$ tel que $f \leq h$ et $g \leq h$. Ainsi $(a,i), (b,j) \in V_h$. Comme
 $h$ est un graphe de d\'ependance, on a donc ou bien $((a,i),(b,j)) \in E_h$ ou bien
$((b,j),(a,i)) \in E_h$. Par d\'efinition de la concat\'enation dans \G\ on en d\'eduit ou bien
$(a,i) \in V_g$ et $((a,i),(b,j)) \in E_g$ ou bien $(b,j) \in V_f$ et 
$((b,j),(a,i)) \in E_f$. Ainsi ou bien $((a,i),(b,j)) \in E$ ou bien $((b,j),(a,i)) \in E$.

C3: Soient $(a,i),(a,j) \in V$ avec $i<j$. Il existe $g \in K$ tel que $(a,j) \in V_g$. Mais
alors $(a,i) \in V_g$ et $((a,i),(a,j)) \in E_g \sub E$. La r\'eciproque est imm\'ediate.

Il reste \`a montrer que $(V,E) = \sqcup K$. Soit $g \in K$, par construction de $(V,E)$, on
v\'erifie ais\'ement que $g$ est un pr\'efixe de  $(V,E)$. R\'eciproquement soit $h \in \G$ un
majorant de $K$. On a clairement $V \sub V_h$ et $E \sub E_h$. Soit  
$((a,i),(b,j)) \in E_h$ avec $(b,j) \in V$. Il existe $g \in K$ tel que $(b,j) \in V_g$.
Comme $g \leq h$, on en d\'eduit $(a,i) \in V_g \sub V$ et $((a,i),(b,j)) \in E_g \sub E$.
De l\`a $(V,E)$ est un pr\'efixe de $h$.
\item Soit $g \in \G$. On dit que $g$ est domin\'e par un ensemble $V \sub V_g$ de sommets si
$V_g = \{ (a,i) \in V_g \mid \e (b,j) \in V \mbox{\rm\ tel que } ((a,i),(b,j)) \in E_g^+
\}$. 

Montrons que $g \in G$ est premier si et seulement si il est domin\'e par un ensemble de
sommets r\'eduit \`a un singleton.

Soit $g \in \G$ premier. Pour tout sommet $(b,j)$ de $V_g$, soit $g_{(b,j)}$ le graphe de
d\'ependance \'egal \`a la restriction de $g$ aux sommets $(a,i)$ tels que 
$((a,i),(b,j)) \in E_g$. Soit $K = \{ g_{(b,j)} \mid (b,j) \in V_g \}$. L'ensemble $K$
est clairement major\'e par $g$ et est donc coh\'erent. Il admet donc une borne sup\'erieure
\'egale, d'apr\`es la d\'emonstration de la question 5.2, \`a $g$. Comme $g$ est premier, on en
d\'eduit qu'il existe $(b,j) \in V_g$ tel que $g = g_{(b,j)}$ d'o\`u le r\'esultat.

R\'eciproquement soit $g \in \G$ domin\'e par un sommet $(a,i) \in V_g$. Soit $K \sub \G$ tel
que $h = \sqcup K$ existe et $ g \leq   h$. Alors $g$ est la restriction de $h$ \`a
$V_g$. En particulier $(a,i) \in V_h$ et d'apr\`es la d\'emonstration de la question 5.2 il
existe $f \in K$ tel que $(a,i) \in V_f$. Mais alors $g \leq f$ et $g$ est premier.\\

Enfin soit $g \in \G$. D'apr\`es ce qui pr\'ec\`ede, les \'el\'ements premiers inf\'erieurs ou \'egaux
\`a $g$ sont exactement les $g_{(b,j)}$ et $\sqcup \{ g_{(b,j)} \mid (b,j) \in V_g \} = g$. 

\item Montrons qu'un graphe de d\'ependance est compact si et seulement si il est domin\'e par
un ensemble fini de sommets c'est \`a dire s'il est dans $\F$. La preuve est similaire \`a
celle de la question pr\'ec\'edente dont on garde les notations.

Soit $g \in \G$ compact. Pour tout ensemble de sommets $V \sub V_g$, soit $g_V$ le graphe de
d\'ependance \'egal \`a la r\'eunion des $g_{(b,j)}$ pour $(b,j) \in V$. 
Soit $K = \{ g_V \mid V \sub V_g, V \mbox{\rm\ fini} \}$. Si $V, V' \sub V_g$, on
a $\sqcup \{g_V,g_{V'}\} = g_{V \cup V'}$ et $K$ est donc dirig\'e et en particulier 
coh\'erent. Il admet donc une borne sup\'erieure \'egale, d'apr\`es la d\'emonstration de la question
5.2, \`a $g$. Comme $g$ est compact, on en d\'eduit qu'il existe $V$ fini dans $V_g$ tel que
$g = g_V$ d'o\`u le r\'esultat.

R\'eciproquement soit $g \in \G$ domin\'e par un ensemble fini $V$ de sommets. 
Soit $K \sub \G$ dirig\'e tel que $h = \sqcup K$ existe et $g \leq  h$. De mani\`ere
analogue \`a la question pr\'ec\'edente, on en d\'eduit $V \sub V_h$ et d'apr\`es la
d\'emonstration de la question 5.2 il existe $f \in K$ tel que $V \sub V_f$. Mais alors $g
\leq f$ et $g$ est premier.\\

Tout \'el\'ement premier \'etant compact, on d\'eduit de la question pr\'ec\'edente que tout graphe
de d\'ependance est la borne sup\'erieure des \'el\'ements compacts qui lui inf\'erieurs ou \'egaux. 


\item Soit $g \in \G$, d'apr\`es la question pr\'ec\'edente l'ensemble $C(g)$ des \'el\'ements
compacts inf\'erieurs ou \'egaux \`a $g$ est d\'enombrable. On peut donc \'enum\'erer les \'el\'ements de 
$C(g)$ en une suite $(g_n)_{n < \omega}$. On d\'efinit alors inductivement la suite 
croissante $(f_n)_{n < \omega}$ dans $C(g)$ de la mani\`ere suivante : $f_0 = g_0$ et si $f_n$
est d\'efini, on choisit $f_{n+1}$ comme \'etant un majorant de $f_n$ et $g_n$ dans $C(g)$ (un
tel majorant existe car l'ensemble $C(g)$ est coh\'erent d'apr\`es la caract\'erisation de 5.4).
On a alors clairement $g = \sqcup \{ f_n \mid n < \omega \} = \sqcup \{ g_n \mid n < \omega
\}$.

\end{enumerate} 

\section{Equations}
\begin{enumerate} 
\item Le sens "seulement si" r\'esulte de la question 4.1. 

Soit $K$ un ensemble fini de g\'en\'erateurs de $M$. Posons $ A = (K \setminus \{1_M\}) \setminus
(K \setminus \{1_M\})^2$ l'ensemble des \'el\'ements de $K$ ne s'\'ecrivant pas comme produit de
deux \'el\'ements ($\neq 1_M$) de $M$. Il est facile de montrer par r\'ecurrence sur la longueur
que tout \'el\'ement de $K$, et donc de $M$, peut s'\'ecrire comme produit d'un nombre fini
d'\'el\'ements de $A$ : $A$ engendre $M$. Soit $I_A$ la relation d'ind\'ependance sur $A$ d\'efinie
par $(x,y)
\in I_A$ si $xy = yx$ dans $M$. 

Soit $\psi$ la surjection canonique de $A^*$ dans $M$ associant \`a un mot de $A^*$ le produit
dans $M$ de ses \'el\'ements. Par d\'efinition de $I_A$, il est imm\'ediat de v\'erifier que deux mots
$\sim_{I_A}$-\'equivalents de $A^*$ ont la m\^eme longueur et la m\^eme image par
$\psi$. Ainsi $\psi$ induit un homomorphisme surjectif $\psib$ de $\Mr(A,I_A)$ dans $M$.

Montrons que $\psib$ est injectif par r\'ecurrence sur la longueur. Soient $u,v \in
\Mr(A,I_A)$ tels que $\psib(u) = \psib(v)$ et tels que pour tout facteur propre (i.e. $\neq
1_M,u$) $w$ de $u$, $\psib^{-1}(\psib(w))$ se r\'eduit \`a $w$. Si $u \in A \cup \{1_M\}$, alors
$v = u$ puisque par d\'efinition, un \'el\'ement de $A$ ne peut s'\'ecrire comme produit de deux
\'el\'ements. Si $u \not \in A \cup \{1_M\}$, $u=xy$, $v=zt$ avec $x,z \in A$, $y \neq 1_M$,
$t \neq 1_M$. On a dans $M$, $\psib(x)\psib(y) = \psib(z)\psib(t)$, ainsi par hypoth\`ese sur
$M$ et en utilisant la surjectivit\'e de $\psib$, il existe des traces $p,q,r,s \in
\Mr(A,I_A)$ telles que $\psib(x)=\psib(p)\psib(q)$, $\psib(y)=\psib(r)\psib(s)$,
$\psib(z)=\psib(p)\psib(r)$, $\psib(t)=\psib(q)\psib(s)$ et 
$\psib(q)\psib(r)=\psib(r)\psib(q)$. Comme $x,y,z,t$ sont des facteurs propres de $u$, on
peut appliquer l'hypoth\`ese de r\'ecurrence et on en d\'eduit
$x = pq, y = rs, z = pr$ et $t = qs$. 
\begin{itemize}   
\item Si $p \neq 1_M$ ou $s \neq 1_M$, $\psib(qr)$ est un facteur propre de $u$. Par
hypoth\`ese de r\'ecurrence $\psib(q)\psib(r)=\psib(r)\psib(q)$ implique alors
$qr = rq$ dans $\Mr(A,I_A)$. Ainsi $u = pqrs = prqs = v$.
\item Si $p = s = 1_M$, $q = x \in A$ et $r = y \in A$. Alors $qr = rq$ dans $M$ et les
traces $u = qr$ et $v = rq$ sont \'egales dans $\Mr(A,I_A)$.
\end{itemize}  
\item 
\begin{enumerate} 
\item Deux \'el\'ements transpos\'es $u=xy$ et $v=yx$ d'un mono\"{\i}de quelconque sont toujours
conjugu\'es puisque $ux = xv$. Soient $u,v, w$  dans un mono\"{\i}de libre tels que
$uw = wv$. Montrons par r\'ecurrence sur $|w|$ que $u$ et $v$ sont transpos\'es. Le cas $|w| =0$,
est trivial. Si $|w| = |u|$, $u$ et $v$ sont \'egaux \`a $w$ (et donc transpos\'es).  Si $|w| <
|u|$, $u=wu'$ et $v=u'w$ d'o\`u le r\'esultat. Si $|w| > |u|$, $w=uw' = w'v$ et on applique
l'hypoth\`ese de r\'ecurrence \`a $u,v,w'$.
\item Soit $A = \{a,b,c\}$ avec $(a,b) \in D, (b,c) \in D$ et $(a,c) \in I$. Les traces
$abc$ et $cba$ ne sont clairement pas transpos\'ees. Elles sont pourtant conjugu\'ees puisque
$(abc)(aba) = (aba)(cba)$.
\item Soit \M\ un mono\"{\i}de de traces et soit $Tr*$ la cl\^oture transitive de la relation de
transposition dans \M. Soient $u,v, w \in \M$  tels que
$uw = wv$. Montrons par r\'ecurrence sur $|w|$ que $(u,v) \in Tr*$. Si $|w| = 0$, $u=v$ et le
r\'esultat est imm\'ediat. Sinon, d'apr\`es la question 4.1, il existe $p,q,r,s$ telles que $u =
pq, w = rs, w = pr, v = qs$ et $(q,r) \in I$. Si $|r| = |w|$, on a $u = v= q$ et $(u,v) \in
Tr*$. Si $|r| < |w|$, on peut appliquer l'hypoth\`ese de r\'ecurrence \`a $(qp,qs,r)$ (en effet,
comme  $(q,r) \in I$ et $w = rs = pr$, on a $qpr = qrs= rqs$). Ainsi $(qp,qs)
\in Tr*$. Comme
$(pq,qp) \in Tr*$, on en d\'eduit par transitivit\'e que $(u,v) \in Tr*$.
\end{enumerate} 
\item Par contradiction. Parmi toutes les solutions $(u,v)$ non-cycliques et v\'erifiant i)
ou ii) d'\'equations $e=f$
choisissons en une telle que $|uv|$ soit minimale.  Par
sym\'etrie et simplifiabilit\'e, on peut supposer que $e=xe'$, $f=yf'$ et que
$|u| \leq |v|$. En appliquant la question 4.1 \`a $u\theta(e') = v\theta(f')$, on obtient
$u = pq$, $v = ps$ pour des traces $p,q,s$ avec $(q,s) \in I$. Si $I = \emptyset$, on a
$q = 1$ car  $|u| \leq |v|$ et donc $v=us$. Sinon ii) est v\'erifi\'e, et $|u| \leq |v|$
entraine $\lona{u} \leq \lona{v}$ pour toute lettre $a$.  Ainsi 
$\lona{q} \leq  \lona{s}$ pour $a \in \al{q}$ et   $(q,s) \in I$ n'est possible que si $q =
1$. 

Nous avons dans tous les cas $v=us$. Si $s=1$ ou $u=1$, $(u,v)$ est cyclique contrairement \`a
l'hypoth\`ese. Sinon, rempla\c{c}ons l'inconnue $y$ par $xz$. On obtient ainsi une nouvelle 
\'equation $g = h$ en les inconnues $x,z$. Par construction, $(u,s)$ est une solution de 
$g = h$ et $|us| < |uv|$. Si $I = \emptyset$, $(u,s)$ est une solution cyclique par
minimalit\'e de   $|uv|$. Sinon, soient $\alpha, \beta$ tels que $\alpha |u|_a =
\beta |v|_a$ pour tout $a \in A$. Comme $|u| \leq |v|$ et $s \neq 1$, on a 
$\alpha > \beta$ et donc $(\alpha - \beta) |u|_a = \beta |s|_a$ pour tout $a \in A$. Par
minimalit\'e de  $|uv|$, on en d\'eduit que $(u,s)$ est une solution cyclique. Ainsi dans tous
les cas $(u,v=us)$ est une solution cyclique contrairement \`a l'hypoth\`ese.
\item Supposons $(u',v') \not \in I$. Soient $a \in \al{u'}, b \in \al{v'}$ avec $(a,b) \in
D$. D'apr\`es 1.2, $(\pro{u},\pro{v}) = (\pro{u'},\pro{v'})$ est une  solution de $e=f$ dans
$(\Mr\{a,b\},\emptyset)$. D'apr\`es 6.3 i), on en d\'eduit que 
$(\pro{u'},\pro{v'})$ est une solution cyclique et donc que 
$\{a,b\} \subseteq \al{u'} \cap \al{v'}$. Ainsi, $\al{u'} = \al{v'}$.
\item D'apr\`es la question pr\'ec\'edente, il suffit de consid\'erer le cas o\`u $u,v$ sont de m\^eme
alphabet connexe. Soient $a,b \in \al{u}, (a,b) \in D$, d'apr\`es  6.3 i),
$(\pro{u},\pro{v})$ est une solution cyclique de $e=f$ dans
$(\Mr\{a,b\},\emptyset)$. Ainsi il existe $\alpha, \beta > 0$ tels que $\alpha |u|_a =
\beta |v|_a$ et $\alpha |u|_b = \beta |v|_b$.  L'alphabet
$\al{u}$ est connexe donc pour toutes lettres $c,d \in \al{u}$, il existe une suite de
lettres dans $\al{u}$, $a_0=c,a_1,\ldots,a_k=d$ telle que $(a_i,a_{i+1}) \in D$ pour tout $0
\leq i < k$. En appliquant ax $(a_i,a_{i+1})$ le raisonnement fait ci-dessus sur
$(a,b)$, on montre qu'il existe $\alpha, \beta > 0$ tels que $\alpha |u|_c = \beta |v|_c$ et 
$\alpha |u|_d = \beta |v|_d$.  Par cons\'equent on peut appliquer 6.3 ii) et la solution
$(u,v)$ est cyclique.
\end{enumerate} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{sloppy}

\end{document}


\begin{itemize}   
\item
\item
\end{itemize}  


\section{Combinatoire}
\begin{enumerate} 
\item
\item
\item
\item
\item
\end{enumerate}