Mot de Lyndon

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, dans les domaines de la combinatoire et de l'informatique, un mot de Lyndon est un mot qui est strictement plus petit, dans l'ordre lexicographique, que tous ses permutés circulaires.

Les mots de Lyndon doivent leur nom au mathématicien Roger Lyndon qui les a introduits en 1954 sous le nom standard lexicographic sequences[1],[2].

Définitions équivalentes[modifier | modifier le code]

Il existe plusieurs définitions équivalentes.

  • Un mot de Lyndon k-aire de longueur n est un mot à n lettres sur un alphabet totalement ordonné de taille k, et qui est strictement minimal (au sens de l'ordre lexicographique) parmi tous ses conjugués (ou permutés circulaires). Strictement minimal signifie ici qu'il n'apparaît qu'une seule fois dans la liste de ses permutés ; il est donc forcément primitif, c'est-à-dire n'est pas puissance entière d'un autre mot.
  • De manière équivalente, un mot de Lyndon w est caractérisé par la propriété suivante : w est toujours lexicographiquement plus petit que tous ses suffixes non triviaux. En d'autres termes, w est un mot de Lyndon si et seulement si, pour toute factorisation w=uv en deux mots, avec u et v non vides, on a w<v.
  • Une variante de cette caractérisation est la suivante: un mot w de longueur n est un mot de Lyndon si et seulement si, pour tout i avec 0<i<n, le préfixe de longueur i de w est strictement inférieur au suffixe de longueur i de w.
  • Ces définitions impliquent que si w n'est pas une lettre, alors w est un mot de Lyndon si et seulement s'il existe deux mots de Lyndon u et v tels que u<v et w=uv.

Dénombrement[modifier | modifier le code]

Les mots de Lyndon sont des représentants des classes de conjugués de mots primitifs, et sont donc en bijection avec les mots circulaires ou colliers primitifs. Soit M(k,n) le nombre de mots de Lyndon de longueur n sur un alphabet à k lettres. Alors on la formule suivante, aussi appelée formule de Witt dans le contexte des algèbres de Lie :

 M(k,n) = \frac1n\sum_{d\,|\,n}\mu\left(\frac n d\right)k^d

\mu est la fonction de Möbius classique. La fonction M(k,n) a plusieurs interprétations, voir polynôme de colliers (en). Ainsi, M(2 ,n) est le nombre de polynômes irréductibles de degré n sur le corps fini GF(2). Le nombre M(k,n) est la dimension de la composante homogène de degré n de l'algèbre de Lie libre à k générateurs. Enfin, c'est l'exposant de l'identité cyclotomique (en) :

{1 \over 1-k z}=\prod_{j=1}^\infty\left({1 \over 1-z^j}\right)^{M(k,j)}

Cette identité reflète la propriété de factorisation unique décrite ci-dessous[3].

Exemple[modifier | modifier le code]

Sur un alphabet à deux symboles 0,1, les mots de Lyndon, par longueur croissante, forment la suite:

0,1;01;001,011;0001,0011,0111;00001,00011,00101,00111,01011,01111;\cdots

La suite des nombres M(2,n) est

2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335,\cdots

C'est la suite A001037 de l'OEIS.

Algorithme de génération[modifier | modifier le code]

Duval (1988) donne un algorithme efficace pour lister les mots de Lyndon de longueur au plus n sur un alphabet donné de taille k en ordre lexicographique.

Si w est un mot de cette séquence, le mot qui suit w s'obtient comme suit.

  1. Répéter les symboles de w jusqu'à obtenir un mot de longueur exactement n. Soit x le mot obtenu. Alors la i-ème lettre de x est la lettre d'indice \scriptstyle i \bmod(|w|) de w (Ici |w| dénote la longueur de w).
  2. Tant que le dernier symbole de x est la plus grande lettre de l'alphabet, enlever cette lettre.
  3. Remplacer la dernière lettre du mot x par la lettre qui suit dans l'alphabet.

Exemple[modifier | modifier le code]

Partant de w=abc (sur l'alphabet à trois lettres avec a<b<c), et si l'on cherche des mots de longueur au plus 7, on obtient

abcabcb (par (1) puis (3))
abcabcc (par (3))
abcac (par (2) puis (3))
abcacac (par (1) puis (3))

Dans le cas le plus défavorable, la procédure pour le calcul du successeur de w est en O(n). En utilisant des structures de données simples, le temps moyen pour calculer le successeur (plus précisément le coût amorti) est en fait constant. C'est pourquoi la suite de tous les mots de Lyndon de longueut au plus n peut être calculée en un temps proportionnel à la longueur de cette suite[4]. La même procédure peut être employée pour calculer les mots dont la longueur divise n, en ne retenant que ces mots; la complexité reste de même proportionnelle à la longueur de la suite (ceci est intéressant dans le cas du mot de de Bruijn dont il est question plus loin).

Factorisation unique en mots de Lyndon[modifier | modifier le code]

Le résultat suivant est souvent appelé théorème de Chen,Fox et Lyndon[5]

Théorème de factorisation unique — Tout mot est produit, de manière unique, d'une suite décroissante (au sens large) de mots de Lyndon.

La factorisation en mots de Lyndon décroissants est appelée la factorisation de Lyndon du mot.

Exemple[modifier | modifier le code]

Le mot x=0110100110010110 s'écrit

x=011\ 01\ 0011\ 001011\ 0,

et on a x=011> 01> 0011>001011> 0.

L'existence de la factorisation est facile à établir: il suffit d'écrire le mot à factoriser comme produit de ses lettres (qui sont des mots de Lyndon), puis à concaténer deux facteurs consécutifs u et v tels que u<v, tant que c'est possible. Ainsi

0\ 1\ 1\ 0\ 1\ 0\ 0\ 1\to 01\ 1\ 01\ 0\ 01\to 011\ 01\ 001

Algorithme de factorisation[modifier | modifier le code]

La méthode d'agglomération esquissée ci-dessus n'est pas très efficace. Un algorithme de factorisation linéaire en fonction de la longueur du mot, a été donné par Duval (1983)[6]. Il opère sur un mot donné de manière à identifier le plus long préfixe qui est un mot de Lyndon. Ce mot est ajouté à la suite en construction, et l'algorithme continue sur le reste du mot. Par exemple, le mot w=0110100110010110 a comme préfixe le mot 011 qui est un mot de Lyndon. On ne peut déterminer que ce mot est un des éléments de la factorisation de Lyndon de w qu'en examinant les lettres qui suivent.

Plus précisément, l'algorithme maintient un préfixe courant du mot à factoriser et examine la lettre qui suit ce préfixe. Selon le cas, il ajoute la lettre au préfixe, ou au contraire trouve un préfixe de ce préfixe courant qui est un des éléments de la factorisation de Lyndon. Ce mot est retranché, et le calcul se poursuit sur le reste. Formellement, on a :

Soit w un mot de longueur n.

  1. Soit m l'indice de la lettre candidate, qui suit préfixe déjà examiné. Au début, m=1 (les lettres sont numérotées à partir de zéro).
  2. Soit k l'indice de la lettre qui sert à la comparaison. Au début, k=0.
  3. Tant que m<n, comparer w[k] et w[m].
    1. si w[k]=w[m], incrémenter k et m;
    2. si w[k]<w[m], poser k=0 et incrémenter m;
    3. si w[k]>w[m], ajouter le préfixe de longueur m-k à la factorisation de Lyndon, supprimer ce préfixe de w, et poser k=0 et m=1.
  4. Ajouter le mot restant à la liste.

Exemple

Pour le mot w=abbabaab, l'algorithme débute par

\begin{array}{|c|c|c|c|c|}
\hline
k&w[k]&m&w[m]&w[k]\sim w[m]\\\hline
0&a&1&b&<\\
0&a&2&b&<\\
0&a&3&a&=\\
1&b&4&b&=\\
2&b&5&a&>\\\hline
\end{array}

Le facteur obtenu est le préfixe de longueur m-k=3, soit x=abb. L'algorithme reprend avec le mot w=abaab. On obtient

\begin{array}{|c|c|c|c|c|}
\hline
k&w[k]&m&w[m]&w[k]\sim w[m]\\\hline
0&a&1&b&<\\
0&a&2&a&=\\
1&b&3&a&>\\\hline
\end{array}

C'est donc le préfixe y=ab qui est l'élément suivant de la factorisation. On termine pour w=aab par

\begin{array}{|c|c|c|c|c|}
\hline
k&w[k]&m&w[m]&w[k]\sim w[m]\\\hline
0&a&1&a&=\\
1&a&2&b&<\\\hline
\end{array}

et la fin du mot est atteinte. La factorisation de Lyndon est donc (abb)(ab)(aab).

Bien entendu, si la factorisation n'a qu'un seul élément, le mot est un mot de Lyndon. Ceci donne donc aussi une méthode pour tester, en temps linéaire, si un mot est un mot de Lyndon.

Propriétés des factorisations de Lyndon[modifier | modifier le code]

On connaît assez bien les termes extrêmes d'une factorisation de Lyndon: Soit (x_1,x_2,\ldots,x_n) la factorisation de Lyndon d'un mot w; alors

  • x_n est le plus petit suffixe de w pour l’ordre lexicographique;
  • x_n est aussi le plus long suffixe de w qui est un mot de Lyndon;
  • x_1 est aussi le plus long préfixe de w qui est un mot de Lyndon.

Factorisation standard[modifier | modifier le code]

Tout mot de Lyndon w qui n’est pas une lettre se factorise en un produit w=uv de deux mots de Lyndon u et v tels que u<v. La factorisation standard (aussi appelée factorisation standard droite ou factorisation de Shirshov) est la factorisation où v est de longueur maximale, et factorisation standard gauche celle où u est de longueur maximale. Ainsi, le mot

aaabaababb

a les factorisations en mots de Lyndon croissants suivantes :

aaabaababb= (a)(aabaababb)=(aaab)(aababb)=(aaabaab)(abb)=(aaabaabab)(b)

C'est la première qui est la factorisation standard, et la dernière la factorisation standard gauche.

Pour calculer une factorisation, on peut se servir des propriétés suivantes. Soit w un mot de Lyndon qui n'est pas une lettre:

  • Soit u le plus long préfixe propre de w qui est un mot de Lyndon, et soit v tel que w=uv; alors v est un mot de Lyndon et u<v et w=uv est la factorisation standard gauche de w.
  • Soit v le plus long suffixe propre de w qui est un mot de Lyndon, et soit u tel que w=uv; alors u est un mot de Lyndon, u<v et w=uv est la factorisation standard de w.

Le lien entre factorisation standard et factorisation de Lyndon est le suivant. Soit w un mot de Lyndon qui n'est pas une lettre, et soit w' le mot obtenu en supprimant la première lettre de w. Le facteur droit v de la factorisation standard de w est le dernier élément de la factorisation de Lyndon de w'.

Ainsi, pour le mot de Lyndon

w=aabaababb

la factorisation de Lyndon de w'=abaababb est w'=(ab)(aababb). La factorisation standard de w=aabaababb est donc w=(aab)(aababb). Ce mot a aussi la factorisation croissante w=(aabaabab)(b).

Applications algébriques[modifier | modifier le code]

Base des algèbres de Lie libre[modifier | modifier le code]

Les mots de Lyndon ont une application dans la description des algèbres de Lie libre. Les mots de Lyndon permettent de construire une base pour chaque composante homogène de degré fixé de l'algèbre de Lie libre. Cette base est appelée la base de Lyndon (ou de Chen–Fox-Lyndon ou de Lyndon–Shirshov). Elle est obtenue par la bijection \gamma qui associe à un mot de Lyndon v un élément de la base comme suit:

  • Si w est une lettre, alors \gamma(w)=w, vu comme générateur de l'algèbre de Lie libre.
  • Si w est composé de plus d'une lettre, alors \gamma(w)=[\gamma(u),\gamma(v)], où w=uv est la factorisation standard de w et où [,] est le crochet de Lie.

Les mots de Lyndon peuvent être vus comme un cas spécial d'ensemble de Hall (en).

Algèbre de mélange[modifier | modifier le code]

Un théorème de Radford (1979)[7] affirme que l'algèbre des polynômes de mots de Lyndon à coefficients rationnels est une algèbre de mélange. Ceci signifie qu'ils forment une algèbre sur le corps des nombres rationnels, avec pour multiplication le produit de mélange.

Autres applications[modifier | modifier le code]

Transformée de Burrows-Wheeler[modifier | modifier le code]

Les mots de Lyndon sont utilisés pour construire des variantes bijectives[8] de la transformée de Burrows-Wheeler utilisée en compression.

Mots de de Bruijn[modifier | modifier le code]

Il y a une connexion surprenante entre mots de Lyndon et mot de de Bruijn (en). Si on concatène, dans l'ordre lexicographique, les mots de Lyndon sur k lettres dont la longueur divise un entier donné n, on obtient un mot de de Bruijn, c'est-à-dire un mot de longueur k^n qui, vu comme mot circulaire, contient les k^n mots de longueur n comme facteurs, chacun une et une seule fois. De plus, ce mot de de Bruijn est le plus petit, pour l'ordre lexicograpgique, de tous les mots de de Bruijn de longueur n sur k lettres[9].

Par exemple, sur deux lettres, la concaténation, en ordre lexicographique, des mots binaires de longueur divisant quatre est

0 0001 0011 01 0111 1

Mots de Lyndon infinis[modifier | modifier le code]

L'ordre lexicographique s'étend aux mots infinis sur un alphabet totalement ordonné comme suit. Soient x et y deux mots infinis. Alors

x<y

s'il existe un mot fini u, deux lettres a<b et des mots infinis x' et y' tels que

x=uax' et y=uby'.

Ainsi, on a x<y pour x=0000111. . . et y=00010000. . .. On peut aussi comparer des mots finis aux mots infinis. Ainsi, si x est un mot fini et y est un mot infini, alors x<y si x est préfixe de y ou si

x=uax' et y=uby'

pour des lettres a<b et un mot fini x' et un mot infini y'. La même définition vaut mutatis mutandis lorsque x est infini et y est fini.

On définit les mots de Lyndon infinis comme suit[10].

Un mot infini est un mot de Lyndon s'il possède une infinité de préfixes (finis) qui sont des mots de Lyndon.

Exemples[modifier | modifier le code]

1. Le mot infini

ab^\omega

composé de la lettre a suivi que de lettres b est un mot de Lyndon infini si a<b car tous ses préfixes sont des mots de Lyndon.

2. Le mot infini

x=a(ab)b(ab)^2b(ab)^3b\cdots (ab)^nb\cdots

est un mot de Lyndon infini car chaque préfixe a(ab)b(ab)^2b(ab)^3b\cdots (ab)^nb est un mot de Lyndon. En revanche, si on enlève le premier a, le mot obtenu n'a plus que trois préfixes qui sont des mots de Lyndon, à savoir a, ab et abb.

Propriétés[modifier | modifier le code]

On a la même caractérisation que pour les mots de Lyndon finis :

Un mot infini est un mot de Lyndon si et seulement s'il est strictement plus petit que tous ses suffixes propres.

Théorème — Tout mot infini x possède une factorisation unique de l'une des deux formes :

  • x=z_1z_2\cdots z_ny, où z_1\ge z_2\ge \cdots\ge z_n\ge y, z_1,z_2,\ldots, z_n sont des mots de Lyndon finis et y est un mot de Lyndon infini;
  • x=z_1z_2\cdots z_n\cdots, où z_1\ge z_2\ge \cdots\ge z_n\ge \cdots, z_1,z_2,\ldots, z_n,\ldots sont des mots de Lyndon.

Exemple[modifier | modifier le code]

Le mot de Fibonacci

f=01 001 010 01001 01 001 010\cdots

a la factorisation

f=z_1z_2z_3\cdots

z_1=010,\quad z_{n+1}0=0f_{2n-1}f_{2n}\  n\ge1

et les mots z_n sont des mots de Lyndon décroissants[11].

Morphisme de Lyndon[modifier | modifier le code]

Un morphisme f:A^\star\to B^\star est un morphisme de Lyndon[12] s'il préserve les mots de Lyndon, c'est-à-dire si l'image par f d'un mot de Lyndon sur A est un mot de Lyndon sur B.

Un morphisme f:A^\star\to B^\star est croissant si pour tous mots x et y sur A, l'inégalité x\le y implique f(x)\le f(y)

Théorème (Richomme) — Un morphisme f:A^\star\to B^\star est un morphisme de Lyndon si et seulement s'il est croissant et si f(a) est un mot de Lyndon pour toute lettre a de A.

Il est décidable si un morphisme est un morphisme de Lyndon. Ceci résulte du fait qu'il est décidable si un morphisme est croissant. La propriété caractéristique est la suivante (Richomme (2003)):

Soit A=\{a_1,a_2,\ldots,a_n\} avec a_1<a_2<\cdots<a_n. Un morphisme f:A^\star\to B^\star est croissant si et seulement si, pour i=1,\ldots,n-1, on a f(a_ia_n^{k_i})<f(a_{i+1}), où k_i est le plus petit entier tel que |f(a_ia_n^{k_i})|\ge|f(a_{i+1}|.

Références[modifier | modifier le code]

  1. Lyndon (1954)
  2. Knuth (2011) utilise le terme prime word.
  3. Ces relations, notamment entre mots de Lyndon et polynômes irréductibles, sont connues depuis longtemps. Un des premiers articles est peut-être Golomb (1969).
  4. Berstel, Pocchiola (1994).
  5. D'après Berstel, Perrin (2007), ce théorème, même s'il est attribué couramment à Chen, Fox et Lyndon (1958), et peut en effet se déduire de résultats de cet article, n'a pas été formulé explicitement avant Schützenberger (1965).
  6. Une description détaillée, avec justification, est donnée dans Lothaire (2005)
  7. Reutenauer (1993) décrit l'algèbre de mélange en détail.
  8. Voir Kufleitner (2009).
  9. D'après Berstel, Perrin (2007) et Knuth (2011), ce mot a été décrit pour la première fois par Martin (1934), et la connexion entre ce mot et les mots de Lyndon a été observée par Fredricksen, Maiorana (1978).
  10. La définition, et la factorisation décroissante, sont de Siromoney et. al. (1994)
  11. Cet exemple est de Melançon (2000).
  12. Cette terminologie est introduite dans Richomme (2003).

Bibliographie[modifier | modifier le code]

  • Jean Berstel et Dominique Perrin (2007), « The origins of combinatorics on words », European Journal of Combinatorics, vol. 28, no 3,‎ 2007, p. 996–1022 (lien DOI?, lire en ligne) lien Math Reviews
  • Jean Berstel et Michel Pocchiola (1994), « Average cost of Duval's algorithm for generating Lyndon words », Theoretical Computer Science, vol. 132, no 1-2,‎ 1994, p. 415–425 (lien DOI?, lire en ligne) lien Math Reviews
  • Srecko Brlek, Jacques-Olivier Lachaud, Xavier Provençal et Christophe Reutenauer (2009), « Lyndon + Christoffel = digitally convex », Pattern Recognition, vol. 42, no 10,‎ 2009, p. 2239–2246 (lien DOI?, lire en ligne)
  • Kuo-Tsai Chen, Ralph H. Fox et Roger Lyndon (1958), « Free differential calculus. IV. The quotient groups of the lower central series », Annals of Mathematics, 2e série, vol. 68, no 1,‎ 1958, p. 81–95 (lien DOI?) lien Math Reviews
  • Jean-Pierre Duval (1983), « Factorizing words over an ordered alphabet », Journal of Algorithms, vol. 4, no 4,‎ 1983, p. 363–381 (lien DOI?) lien Math Reviews
  • Jean-Pierre Duval (1988), « Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée », Theoretical Computer Science, vol. 60, no 3,‎ 1988, p. 255–283 (lien DOI?) lien Math Reviews
  • Harold Fredricksen et James Maiorana (1978), « Necklaces of beads in k colors and k-ary de Bruijn sequences », Discrete Mathematics, vol. 23, no 3,‎ 1978, p. 207–210 (lien DOI?) lien Math Reviews
  • Solomon W. Golomb (1969), « Irreducible polynomials, synchronization codes, primitive necklaces, and the cyclotomic algebra », dans Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, 1967), Chapel Hill, N.C., Univ. North Carolina Press,‎ 1969, p. 358--370 lien Math Reviews
  • Donald E. Knuth (2011), The Art of Computer Programming, vol. 4A : Combinatorial Algorithms, Part 1, Addison-Wesley,‎ 2011 (ISBN 0-201-03804-8, résumé)
  • Manfred Kufleitner (2009), « On bijective variants of the Burrows-Wheeler transform », dans Jan Holub et Jan Žďárek (éditeurs), Prague Stringology Conference,‎ 2009 (lien arXiv?, lire en ligne), p. 65–69
  • M. Lothaire (1983), Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. « Encyclopedia of Mathematics and its Applications » (no 17),‎ 1983 (ISBN 978-0-201-13516-9, résumé) lien Math Reviews
    Une seconde édition révisée est parue chez Cambridge University Press, dans la collection Cambridge Mathematical Library, en 1997, ISBN 978-0-521-59924-5
  • M. Lothaire (2005), Applied combinatorics on words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (no 105),‎ 2005 (ISBN 978-0-521-84802-2, résumé)
  • Roger C. Lyndon (1954), « On Burnside's problem », Transactions of the American Mathematical Society, vol. 77,‎ 1954, p. 202–215 lien Math Reviews
  • Monroe H. Martin (1934), « A problem in arrangements », Bulletin of the American Mathematical Society, vol. 40, no 12,‎ 1934, p. 859–864 (lien DOI?) lien Math Reviews
  • (en) Guy Melançon (2000), « Lyndon factorization of {S}turmian words », Discrete Mathematics, vol. 210, no 1-3,‎ 2000, p. 137--149 lien Math Reviews
  • David E. Radford (1979), « A natural ring basis for the shuffle algebra and an application to group schemes », J. Algebra, vol. 58, no 2,‎ 1979, p. 432–454 lien Math Reviews
  • Christophe Reutenauer (1993), Free Lie algebras, The Clarendon Press Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (no 7),‎ 1993 (ISBN 978-0-19-853679-6, résumé) lien Math Reviews
  • Gwénaël Richomme (2003), « Lyndon morphisms », Bulletin of the Belgian mathematical society Simon Stevin, vol. 10,‎ 2003, p. 761-785 lien Math Reviews
  • Rani Siromoney, Lisa Mathew, V. R. Dare et K. G. Subramanian (1994), « Infinite Lyndon words », Information Processing Letters, vol. 50,‎ 1994, p. 101-104
  • Marcel-Paul Schützenberger (1965), « On a factorisation of free monoids », Proceedings of the American Mathematical Society, vol. 16,‎ 1965, p. 21–24 lien Math Reviews

Liens externes[modifier | modifier le code]