\documentclass[a4paper]{article}
\usepackage{entete}
\author{Référence~: Bruno \textsc{Petazzoni}, 16 problèmes d'informatique}
\title{Le théorème du sous-mot}
\date{2011-2012}

\begin{document}
\maketitle

On définit la relation $<$ sur les mots par~: si $u=u_1\ldots u_n$ et $v=v_1\ldots v_m$, on a $u<v$ {\em si et seulement si} il existe une application strictement croissante $f$ de $\Lbrack 1,n \Rbrack$ sur $\Lbrack 1,m \Rbrack$ telle que $u_i = v_{f(i)}$.

Pour un mot $w$ et un langage $L$, on notera $L_w$ l'ensemble des sur-mots de $w$, \ie{} $$L_w = \{v \in \Sigma^*~|~w < v\}.$$

Pour un langage $L$, on notera $\hat L$ l'ensemble des sur-mots des mots de $L$, et $SM(L)$ l'ensemble des sous-mots des mots de $L$.

Enfin, on appellera {\em antichaîne} sur $\Sigma$ un langage $L$ dont les mots ne sont pas comparables deux à deux pour $<$.

\begin{thm}[du sous-mot]
    Si $L \in \mathfrak p(\Sigma^*)$, alors $SM(L)$ est rationnel.
\end{thm}

\begin{proof}
    La démonstration repose sur le~:
    \begin{lem}[de Higman]
        Toute antichaîne sur $\Sigma$ pour $<$ est finie.
    \end{lem}
    
    On se fixe un langage $L$ quelconque.
    \begin{lem}
        $\hat L$ est rationnel.
    \end{lem}

    \begin{prooflem}
        On considère $L_\downarrow$ l'ensemble des mots de $L$ minimaux pour $<$. Alors nécessairement, $L_\downarrow$ est une antichaîne, donc est finie.

        Pour tout mot $u$ de $\hat L$, il existe un mot $w\in L_\downarrow$ tel que $w<u$, et donc finalement~:
        $$\hat L = \bigcup_{w\in L_\downarrow} L_w.$$

        Chaque $L_w$ est rationnel ($L_w = \Sigma^* w_1 \Sigma^* \cdots \Sigma^* w_n \Sigma^*$), et donc par stabilité des langages rationnels par union finie, on a $\hat L$ rationnel.
    \end{prooflem}

    Maintenant, considérons $K = \Sigma^* \backslash SM(L)$. On va montrer que $K=\hat K$, et on aura alors la rationnalité de $K$, et donc de $SM(L)$ par clotûre des langages rationnels par complémentarisation.

    L'inclusion $K \subseteq \hat K$ est triviale.

    Soit donc $x \in \hat K$. Il existe $w \in K$ tel que $w < x$. Alors si $x\in SM(L)$, alors $w$ aussi, ce qui est une contradiction.

    D'où le résultat.
\end{proof}

Montrons le lemme de Higman~:

\begin{proof}
    On suppose que $A$ est une antichaîne infinie sur $\Sigma$. On note alors
    $$q = |\Sigma\text{ et } n = \min_{u\in A} |u|.$$

    On suppose de plus que $q$ et $n$ sont minimaux~: les antichaînes sur un alphabet plus petit que $\Sigma$ sont finies, et celles dont le mot de longueur minimale est plus court que $n$ aussi.
    \begin{enumerate}[1.]
        \item On remarque que $q>1$ et $n>1$
        \begin{prooflem}
            Si $q=1$, alors toute antichaîne ne contient qu'un élément.

            Si $n=1$, alors $u$ de longueur 1 est une lettre, et donc $A \backslash \{u\}$ antichaîne infinie sur $\Sigma\backslash\{u\}$ de taille $q-1$ $\leftarrow$ contradiction avec la minimalité de $q$.
        \end{prooflem}
        \item On fixe $u$ de longueur $n$. On définit $A'$ comme l'ensemble des mots de $A$ qui sont sur-mots de $u[1,n-1]$.

        On a alors $A\backslash A'$ fini, donc $A'$ infini.

        \begin{prooflem}
            Le langage $(A \backslash A') \cup \{u[1,n-1]\}$ est une antichaîne sur $\Sigma$, avec un mot minimal de longueur $n-1$. Par minimalité de $n$, cette antichaîne est finie.
        \end{prooflem}

        \item On énumère $A'$~: $A' = \{v_1,v_2,\ldots,v_i\ldots\}$, et on écrit chaque $v_i$ comme
        $$v_i = z_{i,1} u_1 z_{i,2} u_2 \cdots z_{i,n-1}u_{n-1} z_{i,n},$$
        où pour $j\leqslant n-1$, $z_{i,j} \in (\Sigma\backslash \{u_j\})^*$.

        Alors $z_{i,n} \in (\Sigma\backslash\{u_n\})^*$.
        \begin{prooflem}
            Sinon, on retrouve $u$ dans $v_i$, et donc $u < v_i$ ce qui est impossible par définition d'antichaîne.
        \end{prooflem}

        \item On définit $Z_j = \{ z_{i,j}~|~i\in\N\}$.

        Alors $Z_j$ a un nombre fini d'éléments minimaux pour $<$.

        \begin{prooflem}
            L'ensemble des éléments minimaux de $Z_j$ est une antichaîne, sur un alphabet de cardinale plus petit strictement que $q$, donc est fini.
        \end{prooflem}

        \item Si $Z_j$ est infini, alors à extraction près, on a pour tout $j$~:
        $$z_{i,j} < z_{i+1,j}.$$

        \begin{prooflem}
            Soit $s(1)$ le plus petit indice tel qu'il n'y ait plus d'éléments minimaux~: $z_{s(1),j}$ n'est pas minimal, et donc $\exists s(2) > s(1)$ tel que $z_{s(1),j} < z_{s(2),j}$.

            En itérant le procédé, on construit la fonction $s$ sur $\N$.
        \end{prooflem}

        \item L'un au moins des $Z_j$ est infini.

        \begin{prooflem}
            On a $A' = Z_1 u_1 Z_2 u_2 \cdots Z_{n-1} u_{n-1} Z_n$, et $A'$ infini.
        \end{prooflem}

        \item En applicant les extractions correspondant aux $Z_j$ infinis, on va se retrouver avec des mots tous comparables entre eux. D'où une contradiction avec le fait que $A'$ est une antichaîne. D'où le résultat.
    \end{enumerate}
\end{proof}



\end{document}