« Lemme de Levi » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

VisuelWikicode

Intégrés

Version du 18 septembre 2015 à 20:35

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

Énoncé

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

Soient $x$ , $y$ , $x'$ , $y'$ des mots. Si $xy=x'y'$ , alors il existe un mot $z$ tel que l'on est dans l'un des deux cas suivants :

ou bien $x=x'z$ , $y'=zy$ (si $|x|\leq |x'|$ ) ;
ou bien $x'=xz$ , $y=zy'$ (si $|x|\geq |x'|$ ).

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

Démonstration

Posons

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

,

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

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

,

et de même soit $j$ l'entier tel que

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

.

Si $|x|\leq |x'|$ , alors $i\leq j$ et on a $x=x'z$ , $y'=zy$ avec

z=a_{i+1}\cdots a_{j}

.

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

z=a_{j+1}\cdots a_{i}

.

Extensions

Un monoïde dans lequel le lemme de Levi est vérifié est appelé équidivisible^[3]. L'équidivisibilité ne garantit pas la liberté d'un monoïde. Mais on a la propriété que voici : Un monoïde $M$ est libre si et seulement s'il est équidivisible et si, de plus, il existe un morphisme $\lambda$ de $M$ dans le monoïde additif des entiers naturels tel que $\lambda ^{-1}(0)=1$ ^[4]. Un monoïde qui possède un morphisme $\lambda$ avec la propriété indiqu est appelé gradué, et $\lambda$ est une graduation^[5]. Ainsi, un monoïde est libre si et seulement s'il est équidivisible et gradué.

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

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 Nielsentransformation de Nielsen dans les groupes. Par exemple, si l’on cherche à résoudre l'équation

xu=yv

où $x$ et $y$ sont des mots inconnus, on peut la transformer en supposant par exemple que $|x|\geq |y|$ . Dans ce cas, le lemme de Levi dit qu'il existe un mot $z$ tel que $x=yz$ , l'équation devient $yzu=yv$ , soit $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].

Notes et références

↑ ^{a et b} Thierry Lecroq, « Combinatoire des mots », sur Institut d'électronique et d'informatique Gaspard-Monge. Slide 22.
↑ Friedrich Wilhelm Levi, « On semigroups », Bulletin of the Calcutta Mathematical Society, vol. 36,‎ 1944, p. 141-146.
↑ Aldo de Luca et Stefano Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer Berlin Heidelberg, 1999 (ISBN 978-3-642-64150-3), p. 2
↑ M. Lothaire, Combinatorics on Words, Cambridge University Press, 1997 (ISBN 978-0-521-59924-5), p. 13
↑ Jacques Sakarovitch, Elements of automata theory, Cambridge, Cambridge University Press, 2009 (ISBN 978-0-521-84425-3), p. 26
↑ Volker Diekert, « More than 1700 years of word equations », dans Conference on Algebraic Informatics, Springer, coll. « Lecture Notes in Computer Science » (n^o 9270), 2015 (ISBN 978-3-319-23020-7, DOI 10.1007/978-3-319-23021-4_2, arXiv 1507.03215), p. 22-28

Article connexe

Monoïde des traces

[lecroq-1] {a et b} Thierry Lecroq, « Combinatoire des mots », sur Institut d'électronique et d'informatique Gaspard-Monge. Slide 22.

[2] Friedrich Wilhelm Levi, « On semigroups », Bulletin of the Calcutta Mathematical Society, vol. 36,‎ 1944, p. 141-146.

[LucaVarricchio2011-3] Aldo de Luca et Stefano Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer Berlin Heidelberg, 1999 (ISBN 978-3-642-64150-3), p. 2

[Lothaire1997-4] M. Lothaire, Combinatorics on Words, Cambridge University Press, 1997 (ISBN 978-0-521-59924-5), p. 13

[5] Jacques Sakarovitch, Elements of automata theory, Cambridge, Cambridge University Press, 2009 (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 » (n^o 9270), 2015 (ISBN 978-3-319-23020-7, DOI 10.1007/978-3-319-23021-4_2, arXiv 1507.03215), p. 22-28

[1]

[2]

[3]

[4]

[5]

[6]

@@ Ligne 1 : / Ligne 1 : @@
 Le '''lemme de Levi''' est un résultat d'[[informatique théorique]] et de [[combinatoire des mots]].
+== Énoncé ==
 L'énoncé est le suivant<ref name=lecroq>
-{{lien web|url=http://www-igm.univ-mlv.fr/~lecroq/m1ita/combinatoire-des-mots.pdf|titre=Combinatoire des mots|auteur=Thierry Lecroq|site=[[Institut d'électronique et d'informatique Gaspard-Monge]]}}. Voir slide 22.
+{{lien web|url=http://www-igm.univ-mlv.fr/~lecroq/m1ita/combinatoire-des-mots.pdf|titre=Combinatoire des mots|auteur=Thierry Lecroq|site=[[Institut d'électronique et d'informatique Gaspard-Monge]]}}. Slide 22.
+</ref> :
-</ref>. Pour tous [[mot (mathématiques)|mots]], ''u'', ''v'', ''x'' et ''y'', si ''u.v = x.y'' (où le point dénote la [[concaténation]]), alors il existe un mot ''w'' tel que l'on est dans l'un des deux cas suivants :
-* ou bien  ''u.w = x'' et ''v = wy'' (si ''|u| ≤ |x|''),
+''Soient <math>x</math>,<math>y</math>,<math>x'</math>,<math>y'</math> des [[mot (mathématiques)|mots]]. Si <math>xy=x'y'</math>, alors il existe un mot <math>z</math> tel que l'on est dans l'un des deux cas suivants'' :
-* ou bien '''u = x.w'' et ''w.v = y'' (si ''|u| ≥ |x|'').
+* ''ou bien  <math>x=x'z</math>, <math>y'=zy</math> (si <math>|x|\le |x'|</math>) ;''
+* ''ou bien  <math>x'=xz</math>, <math>y=zy'</math> (si <math>|x|\ge |x'|</math>).''
 Le lemme porte le nom de [[Friedrich Wilhelm Levi]]<ref name=lecroq/> qui le publia en 1944<ref>
@@ Ligne 15 : / Ligne 17 : @@
  | volume = 36
  | année = 1944}}.</ref>.
+== Démonstration ==
+Posons
+:<math>w=xy=x'y'=a_1a_2\cdots a_n</math>,
+où les <math>a_k</math> sont des lettres. Soit <math>i</math> l'entier tel que
+:<math>x=a_1a_2\cdots a_i, y=a_{i+1}\cdots a_n</math>,
+et de même soit <math>j</math> l'entier tel que
+:<math>x'=a_1a_2\cdots a_j, y'=a_{j+1}\cdots a_n</math>.
+Si <math>|x|\le |x'|</math>, alors <math>i\le j</math> et on a <math>x=x'z</math>, <math>y'=zy</math> avec
+:<math>z=a_{i+1}\cdots a_j</math>.
+Si au contraire <math>|x|\ge |x'|</math>, alors <math>i\ge j</math> et on a <math>x'=xz</math>, <math>y=zy'</math> avec
+:<math>z=a_{j+1}\cdots a_i</math>.
+== Extensions ==
+Un [[monoïde]] dans lequel le lemme de Levi est vérifié est appelé ''équidivisible''<ref name="LucaVarricchio2011">{{ouvrage|author1=Aldo de Luca|author2=Stefano Varricchio|title=Finiteness and Regularity in Semigroups and Formal Languages|year=1999|publisher=Springer Berlin Heidelberg|isbn=978-3-642-64150-3|page=2}}</ref>. L'équidivisibilité ne garantit pas la liberté d'un monoïde. Mais on a la propriété que voici : Un monoïde <math>M</math> est libre si et seulement s'il est équidivisible et si, de plus, il existe un morphisme <math>\lambda</math> de <math>M</math> dans le monoïde additif des entiers naturels tel que <math>\lambda^{-1}(0)=1</math><ref name="Lothaire1997">{{ouvrage|author=M. Lothaire|title=Combinatorics on Words|year=1997|publisher=Cambridge University Press|isbn=978-0-521-59924-5|page=13}}</ref>. Un monoïde qui possède un morphisme <math>\lambda</math> avec la propriété indiqu est appelé ''gradué'', et <math>\lambda</math> est une graduation<ref>{{ouvrage | last=Sakarovitch | first=Jacques | title=Elements of automata theory  | location=Cambridge | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 |page=26 }}</ref>. Ainsi, un monoïde est libre si et seulement s'il est équidivisible et gradué.
+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ïde des traces|monoïdes de traces]].
+== Équations entre mots ==
+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
+{{Lien|trad=Nielsen transformation|transformation de Nielsen}} dans les groupes. Par exemple, si l’on cherche à résoudre l'équation
+:<math>xu=yv</math>
+où <math>x</math> et <math>y</math> sont des mots inconnus, on peut la transformer en supposant par exemple que <math>|x|\ge |y|</math>. Dans ce cas, le lemme de Levi dit qu'il existe un mot <math>z</math> tel que <math>x=yz</math>, l'équation devient <math>yzu=yv</math>, soit <math>zu=v</math>. 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<ref>{{chapitre|auteur = Volker Diekert | titre chapitre = More than 1700 years of word equations | titre ouvrage = Conference on Algebraic Informatics | collection = Lecture Notes in Computer Science | numéro dans collection = 9270 | éditeur =  Springer | année = 2015 | isbn =  978-3-319-23020-7 | arxiv = 1507.03215 | doi = 10.1007/978-3-319-23021-4_2 | id= Die15| passage = 22-28}}</ref>.
 == Notes et références ==
 {{Références}}
+== Article connexe ==
+*[[Monoïde des traces]]
 {{Portail|informatique théorique|mathématiques}}