% Time-stamp: <squelette.tex   2 Feb 2007 17:44:19>

\documentclass{article}

% Pour les accents dans les fichiers
\usepackage[T1]{fontenc}        % Codage des fontes
\usepackage[latin1]{inputenc}   % Codage du fichier
\usepackage[francais]{babel}    % Pour du français
% Packages AMS très utiles
\usepackage{amssymb,amsfonts,amsthm,amsmath}

% Package pour la fabrication d'un index
%\usepackage{makeidx}

% Pour les dessins d'automates éventuellement
% Il faut avoir télécharger gastex.sty et gastex.pro
% http://www.lsv.ens-cachan.fr/~gastin/gastex/gastex.html
%\usepackage{gastex}

% Pour les algorithmes éventuellement
%\usepackage[plain]{algorithm}   
%\usepackage[noend]{algorithmic} 

% Package de dessin
% \usepackage{pstricks,pst-node,pst-tree}

% Package pour avoir des liens hyper-texte dans les fichiers Pdf
% A mettre en dernier
% Pose parfois problème
%\usepackage[a4paper,ps2pdf]{hyperref}

% Définitions d'environements pour les théorèmes, lemmes, définitions, ...
% Tous les environnements partagent la même numérotation
\theoremstyle{plain}
\newtheorem{theoreme}{Théorème}
\newtheorem{lemme}[theoreme]{Lemme}
\newtheorem{proposition}[theoreme]{Proposition}
\newtheorem{corollaire}[theoreme]{Corollaire}
\theoremstyle{definition}
\newtheorem{definition}[theoreme]{Définition}
\theoremstyle{remark}
\newtheorem{exemple}[theoreme]{Exemple}


% Les éléments suivants founiussent les éléments à la commande \maketitle
% Titre
\title{Codes}
% Auteur
\author{Auteur}
% Date optionnelle
% \date{en retard}

\begin{document}

% Mise en place du titre
\maketitle

\section{Codes}
Pour cette partie, on pourra consulter \cite{BerstelPerrin84}. De manière
intuitive, un ensemble~$X$ de mots est un code si tout mot a au plus une
décomposition en produit de mots de~$X$.
\begin{definition} 
  Un ensemble $X \subset A^*$ est un
  \emph{code} sur~$A$ si pour tous entiers $m,n\ge0$ et toute suite
  $x_1,\ldots,x_m,x'_1,\ldots,x'_n$ de mots de~$X$, l'égalité $x_1\cdots
  x_m = x'_1\cdots x'_n$ implique les égalités $m = n$ et $x_i = x'_i$
  pour $1 \le i \le m$.
\end{definition}

\begin{exemple}
  L'ensemble $\{aa, baa, ba\}$ est un code sur l'alphabet $A = \{a,b\}$.
  Par contre, l'ensemble $\{a, ab, ba\}$ n'est pas un code car le mot
  $w = aba$ a les deux décompositions $(ab)a = a(ba)$.  L'ensemble $X =
  a^*b$ est un code infini.
\end{exemple}

Soit $X$ un code sur~$A$ et soit un alphabet~$B$ en bijection avec~$X$ par
une fonction $\mu : B \rightarrow X$.  La fonction~$\mu$ se prolonge en un
morphisme de~$B^*$ dans~$X^*$ en posant $\mu(b_1\cdots b_n) =
\mu(b_1)\cdots \mu(b_n)$ pour tout mot $b_1\cdots b_n$ de~$B^*$.  La
fonction ainsi prolongée est encore bijective si et seulement si $X$ est un
code.  Lorsque $X$ est un code, le monoïde~$X^*$ est alors isomorphe au
monoïde libre~$B^*$.

Soit $A$ un alphabet.  On appelle \emph{sous-monoïde} de~$A^*$ un
ensemble~$M$ de mots tels que $\varepsilon \in M$ et $M\!M \subseteq M$.  La
dernière inclusion est en fait une égalité puisque $\varepsilon \in M$
implique l'inclusion inverse $M \subseteq M\!M$.  Pour des définitions plus
générales de monoïde et de sous-monoïde, on pourra se reporter à la
section~\ref{sec:rec-morph}.

% Pour inclure cette figure, il faut enlever les % en début de ligne
% et inclure le package gastex au début du fichier

% \begin{figure}[htbp]
%   \begin{center}
%     \gasset{Nw=1,Nh=1,Nfill=y,AHnb=0}
%     \begin{picture}(25,12)(0,-3)
%     \node(0)(0,0){}
%     \node(1)(10,0){}
%     \node(2)(22,0){}
%     \node(3)(32,0){}
%     \drawedge(0,1){$v$}
%     \drawedge(1,2){$u$}
%     \drawedge(2,3){$v$}
%     \drawedge[curvedepth=6](0,1){}
%     \drawedge[curvedepth=6](1,3){}
%     \drawedge[curvedepth=-6](0,2){}
%     \drawedge[curvedepth=-6](2,3){}
%     \end{picture}
%   \end{center}
%   \caption{Diagramme des mots $uv$, $vu$ et~$v$}
%   \label{fig:code-free}
% \end{figure}

\begin{definition}
  Un sous-monoïde~$M$ de~$A^*$ est \emph{libre} si pour tous mots
  $u$ et $v$ sur~$A$, les appartenances $uv, vu, v \in M$ impliquent
  $u \in M$.
\end{definition}

Le diagramme des mots $uv$, $vu$, et~$v$ est représenté à la
figure~\ref{fig:code-free}.  Cette définition est justifiée par la
proposition suivante.
\begin{proposition}
  Un sous-monoïde~$M$ de~$A^*$ est libre si et seulement si $M = X^*$ 
  pour un code~$X$ sur~$A$.
\end{proposition}

\begin{lemme}
  Pour tout sous-monoïde~$M$ de~$A^*$, l'ensemble $X = (M-\varepsilon) -
  (M-\varepsilon)^2$ est un ensemble minimal de générateurs.
\end{lemme}
\begin{proof}
  On montre facilement par récurrence sur la longueur que tout mot~$w$
  de~$M$ se décompose $w = x_1\cdots x_n$ où $x_i \in X$.  Si $w$ se
  décompose $w = w_1w_2$ où $w_1,w_2 \in M-\varepsilon$, on applique
  l'hypothèse de récurrence à $w_1$ et~$w_2$ pour obtenir une décomposition
  de~$w$.  Si $w$ n'a pas décomposition $w = w_1w_2$, il appartient à~$X$.

  Réciproquement, soit un ensemble~$Y$ tel que $M = Y^*$.  Il est clair que
  tout mot~$x$ de~$X$ appartient à~$Y$.  Sinon $x$ s'écrit $x = y_1\cdots
  y_n$ avec $n \ge 2$ ce qui contredit le fait que $x$ est indécomposable
  dans~$M$.
\end{proof}

\begin{proof}[{\proofname} de la proposition]
  Supposons d'abord que $M = X^*$ où $X$ est un code.  Soient $u$ et $v$
  des mots tels que $uv, vu, v \in M$.  Les mots $uv$ $vu$ et~$v$ se
  décomposent en produits de mots de~$X$.  On considère alors le mot $w =
  vuv$ de~$M$.  Pour que ce mot ait une seule décomposition, il faut que la
  décomposition de $uv$ soit faite d'une décomposition de~$u$ suivie de
  celle de~$v$.

  Réciproquement soit $M$ un sous-monoïde libre de~$A^*$.  Soit $X$
  l'ensemble $X = (M-\varepsilon) - (M-\varepsilon)^2$.  D'après le lemme
  précédent, on a l'égalité $M = X^*$.  Supposons par l'absurde que $X$ ne
  soit pas un code et soit $z$ un mot de longueur minimale ayant une double
  factorisation $z = x_1\cdots x_m = x'_1\cdots x'_n$.  Par définition
  de~$z$, on a $x_1 \neq x'_1$ et par symétrie on peut supposer que $x'_1 =
  x_1u$ pour un mot $u \neq \varepsilon$.  On pose alors $v = x'_2\cdots
  x'_nx_1$ et on vérifie que $vu = x'_2\cdots x'_nx'_1$, $uv = x_2\cdots
  x_nx_1$ et que $uv, vu, v \in M$.  Puisque $M$ est libre, le mot~$u$
  appartient à~$M$ et ceci contredit la minimalité de~$z$.
\end{proof}

La définition d'un sous-monoïde libre entraîne qu'une intersection
quelconque de sous-monoïdes libres est encore un sous-monoïde libre.  Il
s'ensuit que pour tout langage~$L$ de~$A^*$, il existe un plus petit
sous-monoïde libre contenant~$L$, appelé \emph{enveloppe libre}.

\begin{proposition}
  Soit $X$ un ensemble fini de mots.  Si $X$ n'est pas un code, l'enveloppe
  libre de~$X$ est engendrée par un ensemble~$Y$ tel que $|Y| \le |X| - 1$.
\end{proposition}
\begin{proof}
  Soit $M$ l'enveloppe libre de~$X$ et soit $Y$ le code tel que $M =
  Y^*$.  Tout mot $x$ de~$X$ se décompose $x = y_1\cdots y_n$ avec
  $y_1,\ldots,y_n \in Y$.  On définit la fonction $f : X \rightarrow Y$ en
  posant $f(x) = y_1$ pour tout mot $x \in X$.  On montre que la
  fonction~$f$ est surjective mais mais pas injective.  Supposons par
  l'absurde que $f$ n'est pas surjective.  Si $y$ n'appartient pas
  à~$f(X)$, alors on a l'inclusion $X \subset \varepsilon + (Y-y)Y^*$.  On
  pose alors $Z = (Y-y)y^*$ et on montre facilement que $X \subseteq Z^* =
  \varepsilon + (Y-y)Y^*$ ce qui contredit le fait que $Y^*$ est
  l'enveloppe libre de~$X$.  Si $X$ n'est pas un code, il existe une
  relation $z = x_1\cdots x_m = x'_1\cdots x'_n$ avec $x_1 \neq x'_1$.  On
  vérifie que $f(x_1) = f(x'_1)$ car le mot~$z$ a une unique factorisation.
\end{proof}

Le corollaire suivant décrit les codes à deux mots.  L'équivalence entre
les deuxième et troisième propositions se montre directement par récurrence
sur la longueur de~$uv$.
\begin{corollaire}
  Pour deux mots $u$ et $v$, les propositions suivantes sont équivalentes.
  \begin{itemize}
  \item L'ensemble $\{u, v\}$ n'est pas un code.
  \item Il existe un mot $w$ tel que $u,v \in w^*$.
  \item Les mots $u$ et $v$ vérifient $uv = vu$.
  \end{itemize}
\end{corollaire}

% Bibliographie
% Style de la bibliographie
\bibliographystyle{plain}
% Nom du fichier de bibiographie (sans le .bib)
\bibliography{squelette}

\end{document}
