Lemme de Levi

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

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

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}}$.

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].

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

• Monoïde des traces