\documentstyle[12pt]{article}
%\pagestyle{empty}



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

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

\newcommand{\fnf}{{\rm fnf}}
\newcommand{\fnl}{{\rm fnl}}

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

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

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


\newcommand{\lon}[1]{|#1|}
\newcommand{\lona}[1]{|#1|_a}
\newcommand{\al}[1]{{\rm alph}(#1)}
\newcommand{\ali}[1]{{\rm alphinf}(#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 Math\'ematiques de l'informatique} 

\vspace{0.5cm}

(dur\'ee 6 heures)

\vspace{1cm}
\end{center}


Ce probl\`eme a pour objet l'\'etude de quelques aspects de la th\'eorie des
traces qui est un des mod\`eles les plus \'etudi\'es du parall\'elisme.\\

Dans tout le probl\`eme, $A$ d\'esigne un alphabet fini. Un mot $u$ sur $A$ est
une suite finie $(a_1,\ldots,a_n)$. Ce mot sera not\'e simplement $u = a_1
\ldots a_n$ si aucune confusion n'est possible. L'entier $n$ est la longueur du
mot $u$, not\'ee $\lon{u}$. Le mot vide, not\'e $1$, est l'unique mot de longueur nulle. Pour
toute lettre $a$ de $A$, le nombre d'occurrences de la lettre $a$ dans le mot
$u$ est not\'e $\lona{u}$. Le sous-ensemble de $A$ constitu\'e des lettres ayant
au moins une occurrence dans le mot $u$ est appel\'e alphabet du mot $u$ et est
not\'e $\al{u}$. L'ensemble de tous les mots sur un alphabet $A$ muni de
l'op\'eration binaire de concat\'enation (i.e. de ``mise bout \`a bout'') a une structure de
mono\"{\i}de dont l'\'el\'ement neutre est le mot vide. C'est le mono\"{\i}de
libre engendr\'e par $A$, not\'e $A^*$. La concat\'enation de $u,v \in A^*$ est 
not\'ee simplement $uv$.


On munit $A$ d'une relation $I \sub A \times A$ anti-r\'eflexive et sym\'etrique, dite relation
d'ind\'ependance. Le compl\'ementaire de $I$ est la relation de d\'ependance $D = (A \times A)
\setminus I$. Intuitivement deux actions ind\'ependantes peuvent \^etre ex\'ecut\'ees simultan\'ement
par des processeurs distincts. Deux sous-ensembles $B$ et $C$ de $A$ sont dits ind\'ependants
si $B \times C \sub I$. Deux mots $u,v \in A^*$ sont dits ind\'ependants si leurs alphabets
$\al{u}$ et $\al{v}$ le sont. Par abus de notation, on note alors simplement $(u,v) \in I$. 

La relation $I$ induit une relation binaire $R$ sur $A^*$ d\'efinie par : \[ R =
\{ (uabv,ubav) \mid u,v \in A^*, (a,b) \in I \} \] La cl\^oture r\'eflexive et
transitive de la relation $R$ est not\'ee $\eqi$ ou simplement $\sim$. Deux mots $u,v$ de
$A^*$ v\'erifiant $u \eqi v$ sont dits $\eqi$-\'equivalents ou simplement \'equivalents.\\

\noindent {\bf Exemple 1} : Soit $A = \{a,b,c,d\}$ et $I = \{(a,b), (b,a), (b,c),
(c,b)\}$. Nous avons alors
$aabcbcd \eqi baaccbd \eqi aabbccd$. Les mots $acaa$ et $bb$ sont ind\'ependants,
par contre les mots $acaa$ et $bd$ ne le sont pas. 

On note \M\ le quotient du mono\"{\i}de libre $A^*$ par la relation d'\'equivalence $\eqi$. Un
\'el\'ement de \M\ est appel\'e trace et \M\ est le mono\"{\i}de des traces engendr\'e par $A$ et $I$.

\vspace{0.5cm}




\section{Combinatoire}

\begin{enumerate}
\item Soient $u,v$ deux mots \'equivalents. Montrer que $\lona{u} = \lona{v}$
pour toute lettre $a$ de $A$ et que $\al{u} = \al{v}$ et $\lon{u} = \lon{v}$. 
\item Si $B \sub A$, on note $\Pi_B$ la projection de $A^*$ sur $B^*$ effa\c{c}ant toutes
les lettres n'appartenant pas \`a $B$. Montrer que deux mots sont \'equivalents
si et seulement si $\pro{u} = \pro{v}$ pour tout couple $(a,b) \in D$.
\item En d\'eduire un algorithme lin\'eaire en la longueur du mot pour d\'ecider
si deux mots sont \'equivalents.
\item Montrer que si $u,v,x$ et $y$ sont des mots v\'erifiant $xuy \eqi xvy$
alors $u \eqi v$.
\item Soit $u$ un mot. Une lettre $a$ est dite minimale dans $u$, on note alors
$a \in \mini{u}$, si $u=u'au''$ avec $(a,u') \in I$. Montrer que $a \in
\mini{u}$ si et seulement si : \[
\f b \in A, (a,b) \in D \Lra \pro{u} \mbox{\rm\ commence par la lettre } a
\]
\item D\'eterminer un algorithme qui \'enum\`ere tous les mots \'equivalents \`a
un mot donn\'e. Quelle est la complexit\'e de cet algorithme dans le pire des cas?

\end{enumerate}

\section{Formes normales} On munit maintenant l'alphabet $A$ d'une relation
d'ordre total $<$. Cette relation d\'efinit une relation d'ordre total sur
$A^*$ (not\'ee encore $<$ par abus de notation), dit ordre lexicographique, par
$u < v$ si ou bien $v = uw$ avec $w \neq 1$ ou bien $u = xay, v = xbz$ avec $a,b \in A$ et
$a<b$. Un mot
$u$ est dit sous forme normale lexicographique (\fnl\ en abr\'eg\'e) s'il est plus petit que tout
autre mot \'equivalent : \[
\f v \in A^*, u \eqi v \Lra u = v \mbox{\rm\ ou } u < v \]
\begin{enumerate}
\item D\'eterminer un algorithme lin\'eaire en la longueur du mot calculant l'unique mot sous
\fnl\ \'equivalent \`a un mot donn\'e. 
\end{enumerate}
Un mot non vide $u$ est dit sous forme normale de Foata (\fnf\ en abr\'eg\'e) si
$u = u_1 \ldots u_n$ avec, pour tout $i$ dans $\{1,\ldots,n\}$ : 
\begin{description}
\item [F0] $\f a \in \al{u_i}, \lona{u_i} = 1$
\item [F1] $\f a, b \in \al{u_i}, a=b$ ou $(a,b) \in I$ 
\item [F2] $u_i$ est un mot sous \fnl
\item [F3] si $i \geq 2$, $\forall b \in \al{u_i}$, $\exists a \in \al{u_{i-1}}$ tel
que $(a,b) \in D$
\end{description}
\begin{enumerate}
\setcounter{enumi}{1}
\item Un mot sous \fnl\ est-il toujours sous \fnf? Et r\'eciproquement?
\item Montrer qu'il existe un unique mot sous \fnf\ \'equivalent \`a un mot donn\'e.
\item D\'eterminer un algorithme lin\'eaire en la longueur du mot calculant
l'unique mot sous \fnf\ \'equivalent \`a un mot donn\'e. 
\end{enumerate}



\section{Reconnaissables} Soit $M$ un mono\"{\i}de d'\'el\'ement neutre $1_M$.

Un sous-ensemble $X \sub M$ est dit reconnaissable s'il existe un morphisme
$\eta$ de $M$ dans un mono\"{\i}de fini $S$ et un sous-ensemble $F \sub S$ tels
que $X = \eta^{-1}(F)$. On dira aussi que le morphisme $\eta$ reconna\^{\i}t
$X$. L'ensemble des sous-ensembles reconnaissables de $M$ est not\'e 
${\rm Rec}(M)$.

La concat\'enation de $K, L \sub M$ est d\'efinie par :
\[ KL = \{ kl \mid k \in K, l \in L \} \]
et l'it\'eration de $K \sub M$ par :
\[ K^* = \bigcup_{n \geq 0}K^n \mbox{\rm\ o\`u } K^0 = \{1_M\} \mbox{\rm\ et }
K^{n+1} = K^nK \mbox{\rm\ pour tout } n \geq 0 \]
L'ensemble des parties rationnelles de $M$, not\'e ${\rm Rat}(M)$,
est la plus petite famille de parties contenant les parties finies et close par union,
concat\'enation et it\'eration. 

Le th\'eor\`eme de Kleene assure que dans le mono\"{\i}de libre, les langages rationnels et les
langages reconnaissables co\"{\i}ncident : $\reca = \rata$.

Cette partie du probl\`eme et la suivante ont pour objet d'\'etablir un \'equivalent de ce
th\'eor\`eme pour les mono\"{\i}des de traces. \\

D'apr\`es la question 1.1 on peut d\'efinir sans ambiguit\'e l'alphabet d'une trace et son nombre
d'occurrences d'une lettre donn\'ee, on \'etend alors les notations
$\al{\ }$, $\lon{\ }$ et $\lona{\ }$ aux \'el\'ements de \M. Si $u,v \in \M$ sont deux traces,
on notera encore $(u,v) \in I$ si $\al{u}$ et $\al{v}$ sont ind\'ependants. 

Une trace $t \in \M$ est dite connexe si la relation de d\'ependance $D$ restreinte \`a
$\al{t}$, c'est \`a dire le graphe $(\al{t}, D \cap (\al{t} \times \al{t}))$, est un graphe
connexe. La notion de mot connexe est d\'efinie de mani\`ere analogue. Soit $\varphi$ la
surjection canonique de $A^*$ sur \M. Si l'on reprend l'exemple 1 ci-dessus, les traces
$\varphi(abccbd)$ et
$\varphi(bdd)$ sont connexes alors que
$\varphi(abccb)$ et $\varphi(cbb)$ ne le sont pas.

Une composante connexe d'une trace $t$ est une trace connexe non vide $u$ telle que
$t =uv$ avec $(u,v) \in I$. Si $T \sub \M$ est un langage de traces, on note ${\rm c}(T)$
l'ensemble de toutes les composantes connexes des \'el\'ements de $T$.

Sur $\M$, l'it\'eration concurrente $c$-$*$ est alors d\'efinie pour tout langage de traces
$T \sub \M$, par $T^{c-*} = (c(T))^*$. L'ensemble des langages $c-$rationnels de \M, not\'e
$\crat$, est  la plus petite famille de langages de \M\ contenant les langages finis et
close par les op\'erations d'union, concat\'enation et it\'eration concurrente.

\begin{enumerate}
\item Soit $T \sub \M$ un langage de traces. Si $u \in \M$ est une trace, on
note $u^{-1}T$ l'ensemble $\{ v \in \M \mid uv \in T\}$. Montrer que les trois
assertions suivantes sont \'equivalentes. 
\begin{enumerate}
\renewcommand{\theenumii}{\roman{enumii}} 
\item Le langage $T$ est reconnaissable. 
\item L'ensemble $\varphi^{-1}(T)$ est un langage reconnaissable de $A^*$.
\item La famille $\{ u^{-1}T \mid u \in \M\}$ est finie. 
\end{enumerate}
\item Un morphisme $\eta$ d\'efini sur \M\ est dit alphab\'etique si $\al{u}=\al{v}$ d\`es que
$\eta(u) = \eta(v)$. Montrer qu'un langage de traces est reconnaissable si et
seulement si il est reconnu par un morphisme alphab\'etique. 
\item  Montrer que si $T$ est
un langage reconnaissable, le langage ${\rm c}(T)$ est encore reconnaissable.
\item On note $\FNL$ l'ensemble de tous les mots de $A^*$ sous forme normale
lexicographique (cf partie 2). Montrer que $\FNL$ est un langage
reconnaissable de $A^*$. 
\item Soit $w$ un mot de \FNL\ tel que $w^2$ soit aussi dans \FNL. Montrer que $w$ est
connexe.
\item Montrer que $\rec \sub \crat$.

\end{enumerate}

\section{Rang} 
On veut maintenant d\'emontrer r\'eciproquement que tout langage de $\crat$ est dans $\rec$.
\begin{enumerate}
\item Soient $x,y,u_0,\ldots,u_n$ $n+3$ mots de $A^*$. Montrer que les assertions suivantes
sont \'equivalentes. 
\begin{enumerate}
\renewcommand{\theenumii}{\roman{enumii}} 
\item $xy \sim u_0 \ldots u_n$.
\item Il existe des mots $x_0,\ldots,x_n$, $y_0,\ldots,y_n$ tels que :
\begin{itemize}
\item $x \sim x_0 \ldots x_n$, $y \sim y_0 \ldots y_n$ 
\item $u_i \sim x_iy_i$ pour tout $0 \leq i \leq n$ 
\item $(y_i,x_{i+1}\ldots x_n) \in I$ pour tout $0 \leq i < n$
\end{itemize}
\end{enumerate}
\end{enumerate}



Soient $x,y \in A^*$ et $L$ un langage de $A^*$. D'apr\`es la question pr\'ec\'edente, le
produit
$xy$ est \'equivalent \`a un \'el\'ement de $L$ s'il existe des mots
$x_0,y_0,\ldots,x_n,y_n$ de $A^*$ tels que $x \eqi x_0 \ldots x_n$, $y \eqi y_0
\ldots y_n$, $x_0y_0x_1y_1 \ldots x_ny_n \in L$ et 
$(y_i,x_{i+1} \ldots x_n) \in I$ pour tout $0 \leq i < n$. On d\'efinit alors $\rg{x,y,L}$
comme \'etant le plus petit entier $n$ pour lequel une telle factorisation est possible. Le
rang (fini ou infini) d'un langage $L \sub A^*$ est alors
\[
\rg{L} = \mbox{\rm\ max}\{\rg{x,y,L} \mid x,y \in A^*, xy \in
\varphi^{-1}(\varphi(L)) \}
\] 
Un langage $L \sub A^*$ est dit $I$-clos (ou simplement clos) si tout mot \'equivalent \`a un
mot de $L$ est encore dans $L$.
 
\begin{enumerate}
\setcounter{enumi}{1}
\item On consid\`ere l'alphabet $A=\{a,b\}$ et la relation d'ind\'ependance
$I=\{(a,b),(b,a)\}$. Calculer $\rg{\{ab\}^*}$ et $\rg{\{a\}^*\{b\}^*}$. 
\item Soient $L_1, L_2 \sub A^*$ deux langages $I$-clos. Montrer que $\rg{L_1L_2} \leq 1$.
\item Soit $L \sub A^*$ un langage $I$-clos connexe. Montrer que $\rg{L^*} <
2\lon{A}$.
\item Soit $L \sub A^*$ un langage reconnaissable de rang fini. Montrer que
$\varphi(L)$ est un langage reconnaissable de traces. 
\item Que dire de la
r\'eciproque de la question pr\'ec\'edente? 
\item Montrer que $\crat \sub \rec$.
\end{enumerate}

\section{Graphes de d\'ependance} 

On note $\omega$ le cardinal de l'ensemble $\N$ des entiers naturels. L'addition
usuelle dans $\N$ est \'etendue en posant $\omega + n = n + \omega = \omega$ pour tout $n \in
\N \cup \{\omega\}$. Pour $a \in A$ et $n
\in \N \cup \{\omega\}$, on d\'efinit l'ensemble des sommets $V_a(n) = \{ (a,i) \mid i <
n\}$. 

Un graphe de  d\'ependance sur $(A,I)$ est une
paire $g = ((n_a)_{a \in A},E)$  o\`u $n_a \in \N \cup \{\omega\}$ pour tout $a \in A$ et
$E \sub V \times V$ avec $V = \bigcup_{a \in A}V_a(n_a)$ v\'erifiant les trois conditions :
\begin{description}
\item [C1] $E$ est sans cycle : $\f v \in V, (v,v) \not \in E^+$ (o\`u $E^+$ d\'esigne la cl\^oture
transitive de $E$)
\item [C2] $\f a,b \in A$, $\f x \in V_a(n_a)$, $\f y \in V_b(n_b)$ :
\[ (a,b) \in D \Longleftrightarrow
((x,y) \in E \mbox{\rm\ ou } (y,x) \in E \mbox{\rm\ ou } x=y) \]
\item [C3] $\f a \in A$, $\f (a,i), (a,j) \in V_a(n_a)$ :
\[ ((a,i), (a,j)) \in E \Longleftrightarrow i < j \]
\end{description}
L'ensemble des graphes de d\'ependance sur $(A,I)$ est
not\'e \G. Le sous-ensemble de \G\ constitu\'e des graphes ayant un nombre fini de sommets
est not\'e \F. Pour $g = ((n_a)_{a \in A},E_g) \in \G$, on d\'efinit
$\al{g} = \{ a \in A \mid n_a \neq 0 \}$ et $\ali{g} = \{ a \in A \mid n_a = \omega \}$.

 On d\'efinit une op\'eration de concat\'enation partielle dans
\G\ de la mani\`ere suivante. Soient $g = ((n_a)_{a \in A},E_g) \in \G$ et 
$h = ((m_a)_{a \in A},E_h) \in \G$ avec $\ali{g} \times \al{h} \sub I$ (cette condition
est trivialement v\'erifi\'ee si $g \in \F$), la concat\'enation de $g$ et $h$, not\'ee 
$g \cdot h$ est le graphe de d\'ependance $f = ((n_a+m_a)_{a \in A},E_f)$ avec 

$\begin{array}{rl}
E_f = E_g & \bigcup\ \{((a,n_a + i),(b,n_b + j)) \mid ((a,i),(b,j)) \in E_h\} \\
          & \bigcup\ \{((a,i),(b,n_b + j)) \mid (a,b) \in D, i < n_a, j < m_b \}
\end{array}$

\begin{enumerate}
\item Montrer que \F\ muni de la concat\'enation $(\cdot)$ est isomorphe \`a \M.
\end{enumerate}

Soient $g,f \in \G$, $g$ est un pr\'efixe de $f$ s'il existe $h \in \G$ tel que
$f = g \cdot h$. La relation ``\^etre pr\'efixe de'' est une relation d'ordre partiel sur \G\,
not\'ee $\leq$. 

Soit $(Z,\leq)$ un ensemble partiellement ordonn\'e. Un sous-ensemble $Y \sub Z$ est coh\'erent
si pour tout $x,y \in Y$ il existe $z \in Z$  tel que
$x \leq z$ et $y \leq z$. 
Un sous-ensemble non vide $Y \sub Z$ est dirig\'e si pour tout $x,y \in Y$ il
existe $z \in Y$ tel que $x \leq z$ et $y \leq z$.
Un \'el\'ement $x \in Z$ est premier (resp. compact) si pour tout
sous-ensemble (resp. pour tout sous ensemble dirig\'e) $Y \sub Z$ admettant une borne
sup\'erieure $\sqcup Y$, $x \leq \sqcup Y$ entraine l'existence d'un \'el\'ement $y \in Y$ tel que
$x \leq y$.
\begin{enumerate}
\setcounter{enumi}{1}
\item Montrer qu'un ensemble $K \sub \G$ est
coh\'erent si et seulement si il admet une borne sup\'erieure.
\item Caract\'eriser les \'el\'ements premiers de $\G$ et montrer que tout graphe de d\'ependance est
la borne sup\'erieure de l'ensemble des \'el\'ements premiers qui lui sont inf\'erieurs ou \'egaux.
\item Caract\'eriser les \'el\'ements compacts de $\G$ et montrer que tout graphe de d\'ependance est
la borne sup\'erieure de l'ensemble des \'el\'ements compacts qui lui sont inf\'erieurs ou \'egaux.
\item Montrer que tout \'el\'ement de $\G$ est la borne sup\'erieure d'une suite croissante
d'\'el\'ements de $\F$.
\end{enumerate}

\section{Equations} 
\begin{enumerate}
\item Soit $M$ un mono\"{\i}de d'\'el\'ement neutre $1_M$. Une longueur 
 est un morphisme $\gamma$ de $M$ dans \N\ telle que $\gamma^{-1}(0) = \{1_M\}$. Un mono\"{\i}de
$M$ est finiment engendr\'e s'il existe $K$ fini inclus dans $M$ tel que tout \'el\'ement de $M$
est produit d'\'el\'ements de $K$. Montrer qu'un mono\"{\i}de finiment engendr\'e $M$ muni d'une
longueur est isomorphe \`a un mono\"{\i}de de traces si et seulement si, pour tout $x,y,z,t \in M$,
l'\'egalit\'e $xy = zt$ entra\^{\i}ne l'existence de $p,q,r,s \in M$ tels que $x = pq$, $y = rs$, $z
= pr$, $t = qs$ et $qr = rq$. 
\item Soit $M$ un mono\"{\i}de. Deux \'el\'ements $u$ et $v$ de
$M$ sont dits conjugu\'es s'il existe $w$ dans $M$ tel que
$uw = wv$. Les \'el\'ements $u$ et $v$ sont dits transpos\'es s'il existe $x,y$ dans $M$  tels que
$u = xy$ et $v = yx$.
\begin{enumerate}
\item Montrer que les notions de conjugaison et de transposition co\"{\i}ncident si $M$ est un
mono\"{\i}de libre. 
\item Donner un exemple de mono\"{\i}de de traces o\`u ces deux notions sont distinctes.
\item Montrer que dans un mono\"{\i}de de traces, la conjugaison est la cl\^oture transitive de la
relation de  transposition. 
\end{enumerate}
\end{enumerate}

Soit $X = \{x,y\}$ avec $x \neq y$ un alphabet de 2 lettres. Une \'equation
$e=f$ sur $X$ est une paire de mots distincts $e,f \in X^*$. Une solution de
$e=f$ dans $\M$ est un morphisme $\theta: X^* \lra \M$ telle que $\theta(e) = \theta(f)$. Si
une solution $\theta$ est d\'efinie par $\theta(x) = u$ et $\theta(y) = v$, on \'ecrit
simplement que $(u,v)$ est une solution de $e=f$ (dans $\M$). Une solution
$(u,v)$ est dite cyclique s'il existe une trace $t$ telle que $u,v \in t^*$ (i.e. sont des
puissances de~$t$). 

\begin{enumerate}
\setcounter{enumi}{2}
\item Soit $(u,v)$ une solution de $e=f$ dans $\M$. Montrer que $(u,v)$ est cyclique d\`es que
l'une des deux conditions suivantes est satisfaite :
\begin{enumerate}
\renewcommand{\theenumii}{\roman{enumii}} 
\item \M\ est libre c'est \`a dire $I = \emptyset$. 
\item Il existe des nombres entiers
$\alpha, \beta > 0$ tels que $\alpha \lona{u} = \beta \lona{v}$ pour toute lettre
$a$ de $A$.
\end{enumerate}
\item Soit $(u,v)$ une solution de l'\'equation $e=f$. Soit $u'$ (resp. $v'$) une composante
connexe de $u$ (resp. de $v$). Montrer que ou bien $\al{u'} = \al{v'}$ ou bien
$(u',v') \in I$. \item Soit $(u,v)$ une solution de l'\'equation $e=f$. Montrer qu'il existe
des traces deux \`a deux ind\'ependantes et connexes $t_1,\ldots,t_k$ telles que $u,v \in t_1^*
\ldots t_k^*$.
\end{enumerate}

\end{sloppy}

\end{document}

