Lemme de Levi

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

ÉnoncéModifier

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

Lemme de Levi — Soient  ,  ,  ,   des mots. Si  , alors il existe un mot   tel que l'on est dans l'un des deux cas suivants :

  • ou bien  ,   (si  ) ;
  • ou bien  ,   (si  ).

ExempleModifier

Soient anti, constitutionnellement, anticonstitutionnel, lement des mots.
Si anti . constitutionnellement = anticonstitutionnel . lement, et que de plus | anti | | anticonstitutionnel |
alors il existe le mot constitutionnel tel que anticonstitutionnel = anti . constitutionnel et constitutionnellement = constitutionnel . lement

DémonstrationModifier

Posons

 ,

où les   sont des lettres. Soit   l'entier tel que

 ,

et de même soit   l'entier tel que

 .

Si  , alors   et on a  ,   avec

 .

Si au contraire  , alors   et on a  ,   avec

 .

ExtensionsModifier

Monoïde équidivisible et graduéModifier

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   est libre si et seulement s'il est équidivisible et si, de plus, il existe un morphisme   de   dans le monoïde additif des entiers naturels tel que  [4].

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

Autre extensionsModifier

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 motsModifier

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

 

  et   sont des mots inconnus, on peut la transformer en supposant par exemple que  . Dans ce cas, le lemme de Levi dit qu'il existe un mot   tel que  , l'équation devient  , soit  . 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].

HistoriqueModifier

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

Notes et référencesModifier

  1. a et b Thierry Lecroq, « Combinatoire des mots », sur Institut d'électronique et d'informatique Gaspard-Monge. Slide 22.
  2. (en) Aldo de Luca et Stefano Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer Berlin Heidelberg, (ISBN 978-3-642-64150-3), p. 2.
  3. (en) J. D. McKnight Jr. et A. J. Storey, « Equidivisible semigroups », Journal of Algebra, vol. 12, no 1,‎ , p. 24-48 (DOI 10.1016/0021-8693(69)90015-5).
  4. (en) M. Lothaire, Combinatorics on Words, Cambridge University Press, , 238 p. (ISBN 978-0-521-59924-5, lire en ligne), p. 13.
  5. (en) Elements of Automata Theory, Cambridge, Cambridge University Press, , 758 p. (ISBN 978-0-521-84425-3), p. 26.
  6. Volker Diekert, « More than 1700 years of word equations », dans Conference on Algebraic Informatics, Springer, coll. « Lecture Notes in Computer Science » (no 9270), (ISBN 978-3-319-23020-7, DOI 10.1007/978-3-319-23021-4_2, arXiv 1507.03215), p. 22-28
  7. Friedrich Wilhelm Levi, « On semigroups », Bulletin of the Calcutta Mathematical Society, vol. 36,‎ , p. 141-146.

Article connexeModifier