Lemme de Levi

Le lemme de Levi est un résultat d'informatique théorique et de combinatoire des mots.

Énoncé[modifier | modifier le code]

L'énoncé est le suivant^[1] :

Exemple[modifier | modifier le code]

Soient anti, constitutionnellement, anticonstitutionnel, lement des mots.
Si anti . constitutionnellement = anticonstitutionnel . lement, et que de plus | anti |${\displaystyle \leq }$| anticonstitutionnel |
alors il existe le mot constitutionnel tel que anticonstitutionnel = anti . constitutionnel et constitutionnellement = constitutionnel . lement

Démonstration[modifier | modifier le code]

Posons

${\displaystyle w=xy=x'y'=a_{1}a_{2}\cdots a_{n}}$,

où les ${\displaystyle a_{k}}$ sont des lettres. Soit ${\displaystyle i}$ l'entier tel que

${\displaystyle x=a_{1}a_{2}\cdots a_{i},y=a_{i+1}\cdots a_{n}}$,

et de même soit ${\displaystyle j}$ l'entier tel que

${\displaystyle x'=a_{1}a_{2}\cdots a_{j},y'=a_{j+1}\cdots a_{n}}$.

Si ${\displaystyle |x|\leq |x'|}$, alors ${\displaystyle i\leq j}$ et on a ${\displaystyle x'=xz}$, ${\displaystyle y=zy'}$ avec

${\displaystyle z=a_{i+1}\cdots a_{j}}$.

Si au contraire ${\displaystyle |x|\geq |x'|}$, alors ${\displaystyle i\geq j}$ et on a ${\displaystyle x=x'z}$, ${\displaystyle y'=zy}$ avec

${\displaystyle z=a_{j+1}\cdots a_{i}}$.

Extensions[modifier | modifier le code]

Monoïde équidivisible et gradué[modifier | modifier le code]

L'ensemble des mots sur un alphabet donné, muni de la relation de concaténation, forment un monoïde. Le lemme de Levi peut s'appliquer à d'autres exemples de cette structure algébrique.

Un monoïde dans lequel le lemme de Levi est vérifié est appelé équidivisible^[2],[3]. L'équidivisibilité ne garantit pas la liberté d'un monoïde. Mais on a la propriété que voici :

Un monoïde ${\displaystyle M}$ est libre si et seulement s'il est équidivisible et si, de plus, il existe un morphisme ${\displaystyle \lambda }$ de ${\displaystyle M}$ dans le monoïde additif des entiers naturels tel que ${\displaystyle \lambda ^{-1}(0)=\{1\}}$^[4].

Un monoïde qui possède un morphisme ${\displaystyle \lambda }$ avec la propriété indiquée est appelé gradué, et ${\displaystyle \lambda }$ est une graduation^[5]. Ainsi, un monoïde est libre si et seulement s'il est équidivisible et gradué.

Autre extensions[modifier | modifier le code]

Il existe des lemmes à la Levi dans d'autres contextes, par exemple en théorie des graphes, mais aussi dans des classes particulières de monoïdes comme les monoïdes de traces.

Équations entre mots[modifier | modifier le code]

Le lemme de Levi est l'ingrédient de base pour résoudre des équations entre mots. Dans ce contexte, l'application du lemme de Levi est appelé transformation de Nielsen, par analogie avec la transformation de Nielsen dans les groupes. Par exemple, si l’on cherche à résoudre l'équation

${\displaystyle xu=yv}$

où ${\displaystyle x}$ et ${\displaystyle y}$ sont des mots inconnus, on peut la transformer en supposant par exemple que ${\displaystyle |x|\geq |y|}$. Dans ce cas, le lemme de Levi dit qu'il existe un mot ${\displaystyle z}$ tel que ${\displaystyle x=yz}$, l'équation devient ${\displaystyle yzu=yv}$, soit ${\displaystyle zu=v}$. Cette approche produit, de proche en proche, un graphe qui, lorsqu'il est fini, permet de trouver les solutions de l'équation. Une méthode générale de solution a été donné par Makanin. Cette méthode a été grandement améliorée depuis^[6].

Historique[modifier | modifier le code]

Le lemme porte le nom de Friedrich Wilhelm Levi^[1] qui le publia en 1944^[7].

Notes et références[modifier | modifier le code]

Article connexe[modifier | modifier le code]

• Monoïde des traces

• Portail de l'informatique théorique
• Portail des mathématiques