Mot de Lyndon
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
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 est caractérisé par la propriété suivante : est toujours lexicographiquement plus petit que tous ses suffixes non triviaux. En d'autres termes, est un mot de Lyndon si et seulement si, pour toute factorisation en deux mots, avec et non vides, on a .
- Une variante de cette caractérisation est la suivante: un mot de longueur est un mot de Lyndon si et seulement si, pour tout avec , le préfixe de longueur de est strictement inférieur au suffixe de longueur de .
- Une autre définition : est un mot de Lyndon si et seulement si, pour toute factorisation en deux mots, avec et non vides, on a [3].
- Ces définitions impliquent que si n'est pas une lettre, alors est un mot de Lyndon si et seulement s'il existe deux mots de Lyndon et tels que et .
Dénombrement
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 le nombre de mots de Lyndon de longueur sur un alphabet à lettres. Alors on a la formule suivante, aussi appelée formule de Witt dans le contexte des algèbres de Lie :
où est la fonction de Möbius classique. La fonction a plusieurs interprétations, voir polynôme de colliers (en). Ainsi, est le nombre de polynômes irréductibles de degré sur le corps fini . Le nombre est la dimension de la composante homogène de degré de l'algèbre de Lie libre à générateurs. Enfin, c'est l'exposant de l'identité cyclotomique (en) :
Cette identité reflète la propriété de factorisation unique décrite ci-dessous[4].
Exemple
Sur un alphabet à deux symboles , les mots de Lyndon, par longueur croissante, forment la suite:
La suite des nombres est
- 1,
C'est la suite A001037 de l'OEIS.
Algorithme de génération
Duval (1988) donne un algorithme efficace pour lister les mots de Lyndon de longueur au plus sur un alphabet donné de taille en ordre lexicographique.
Si est un mot de cette séquence, le mot qui suit s'obtient comme suit.
- Répéter les symboles de jusqu'à obtenir un mot de longueur exactement . Soit le mot obtenu. Alors la -ème lettre de est la lettre d'indice de (Ici dénote la longueur de ).
- Tant que le dernier symbole de est la plus grande lettre de l'alphabet, enlever cette lettre.
- Remplacer la dernière lettre du mot par la lettre qui suit dans l'alphabet.
Exemple
Partant de (sur l'alphabet à trois lettres avec ), et si l'on cherche des mots de longueur au plus , on obtient
- (par (1) puis (3))
- (par (3))
- (par (2) puis (3))
- (par (1) puis (3))
Dans le cas le plus défavorable, la procédure pour le calcul du successeur de est en . 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 longueur au plus peut être calculée en un temps proportionnel à la longueur de cette suite[5]. La même procédure peut être employée pour calculer les mots dont la longueur divise , 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
Le résultat suivant est souvent appelé théorème de Chen, Fox et Lyndon[6]
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
Le mot s'écrit
- ,
et on a .
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 et tels que , tant que c'est possible. Ainsi
Algorithme de factorisation
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)[7]. 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 a comme préfixe le mot 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 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 un mot de longueur .
- Soit l'indice de la lettre candidate, qui suit préfixe déjà examiné. Au début, (les lettres sont numérotées à partir de zéro).
- Soit l'indice de la lettre qui sert à la comparaison. Au début, .
- Tant que , comparer et .
- si , incrémenter et ;
- si , poser et incrémenter ;
- si , ajouter le préfixe de longueur à la factorisation de Lyndon, supprimer ce préfixe de , et poser et .
- Ajouter le mot restant à la liste.
Exemple
Pour le mot , l'algorithme débute par
Le facteur obtenu est le préfixe de longueur , soit . L'algorithme reprend avec le mot . On obtient
C'est donc le préfixe qui est l'élément suivant de la factorisation. On termine pour par
et la fin du mot est atteinte. La factorisation de Lyndon est donc .
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
On connaît assez bien les termes extrêmes d'une factorisation de Lyndon: Soit la factorisation de Lyndon d'un mot ; alors
- est le plus petit suffixe de pour l’ordre lexicographique;
- est aussi le plus long suffixe de qui est un mot de Lyndon;
- est aussi le plus long préfixe de qui est un mot de Lyndon.
Factorisation standard
Tout mot de Lyndon qui n’est pas une lettre se factorise en un produit de deux mots de Lyndon et tels que . La factorisation standard (aussi appelée factorisation standard droite ou factorisation de Shirshov) est la factorisation où est de longueur maximale, et factorisation standard gauche celle où est de longueur maximale. Ainsi, le mot
a les factorisations en mots de Lyndon croissants suivantes :
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 un mot de Lyndon qui n'est pas une lettre:
- Soit le plus long préfixe propre de qui est un mot de Lyndon, et soit tel que ; alors est un mot de Lyndon et et est la factorisation standard gauche de .
- Soit le plus long suffixe propre de qui est un mot de Lyndon, et soit tel que ; alors est un mot de Lyndon, et est la factorisation standard de .
Le lien entre factorisation standard et factorisation de Lyndon est le suivant. Soit un mot de Lyndon qui n'est pas une lettre, et soit le mot obtenu en supprimant la première lettre de . Le facteur droit de la factorisation standard de est le dernier élément de la factorisation de Lyndon de .
Ainsi, pour le mot de Lyndon
la factorisation de Lyndon de est . La factorisation standard de est donc . Ce mot a aussi la factorisation croissante .
Applications algébriques
Base des algèbres de Lie libre
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 qui associe à un mot de Lyndon un élément de la base comme suit:
- Si est une lettre, alors , vu comme générateur de l'algèbre de Lie libre.
- Si est composé de plus d'une lettre, alors , où est la factorisation standard de 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
Un théorème de Radford (1979)[8] 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
Transformée de Burrows-Wheeler
Les mots de Lyndon sont utilisés pour construire des variantes bijectives[9] de la transformée de Burrows-Wheeler utilisée en compression de données.
Mots de de Bruijn
Il y a une connexion surprenante entre mots de Lyndon et mot de de Bruijn. Si on concatène, dans l'ordre lexicographique, les mots de Lyndon sur lettres dont la longueur divise un entier donné , on obtient un mot de de Bruijn, c'est-à-dire un mot de longueur qui, vu comme mot circulaire, contient les mots de longueur comme facteurs, chacun une et une seule fois. De plus, ce mot de de Bruijn est le plus petit, pour l'ordre lexicographique, de tous les mots de de Bruijn de longueur sur lettres[10].
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
L'ordre lexicographique s'étend aux mots infinis sur un alphabet totalement ordonné comme suit. Soient et deux mots infinis. Alors
s'il existe un mot fini , deux lettres et des mots infinis et tels que
- et .
Ainsi, on a pour et . On peut aussi comparer des mots finis aux mots infinis. Ainsi, si est un mot fini et est un mot infini, alors si est préfixe de ou si
- et
pour des lettres et un mot fini et un mot infini . La même définition vaut mutatis mutandis lorsque est infini et est fini.
On définit les mots de Lyndon infinis comme suit[11].
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
1. Le mot infini
composé de la lettre suivi que de lettres est un mot de Lyndon infini si car tous ses préfixes sont des mots de Lyndon.
2. Le mot infini
est un mot de Lyndon infini car chaque préfixe est un mot de Lyndon. En revanche, si on enlève le premier , le mot obtenu n'a plus que trois préfixes qui sont des mots de Lyndon, à savoir et .
3. Soit le mot de Fibonacci, défini par avec , et pour . Alors le mot est un mot de Lyndon. Le mot est strictement plus grand que tous ses suffixes. Le résultat s'étend à tout mot Sturmien caractéristique.
Propriétés
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 possède une factorisation unique de l'une des deux formes :
- , où , sont des mots de Lyndon finis et est un mot de Lyndon infini;
- , où , sont des mots de Lyndon.
Exemple
a la factorisation
où
et les mots sont des mots de Lyndon décroissants[12].
Morphisme de Lyndon
Un morphisme est un morphisme de Lyndon[13] s'il préserve les mots de Lyndon, c'est-à-dire si l'image par d'un mot de Lyndon sur est un mot de Lyndon sur .
Un morphisme est croissant si pour tous mots et sur , l'inégalité implique
Théorème (Richomme) — Un morphisme est un morphisme de Lyndon si et seulement s'il est croissant et si est un mot de Lyndon pour toute lettre de .
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 avec . Un morphisme est croissant si et seulement si, pour , on a , où est le plus petit entier tel que .
Langage des mots de Lyndon
L'ensemble des mots de Lyndon sur un alphabet donné est un langage formel et, en tant que tel, a sa place dans la hiérarchie de Chomsky. Il a été démontré, en utilisant le lemme d'itération d'Ogden, que ce langage n'est pas algébrique[14]. La même question concernant le langage des mots primitifs est toujours ouverte en 2014[15]. Ces langages sont liés puisque la fermeture, par permutation circulaire, du langage des mots de Lyndon est le langage des mots primitifs, et la fermeture par permutation circulaire est une opération qui préserve l’algébricité des langages algébriques.
Références
- ↑ Lyndon (1954)
- ↑ Knuth (2011) utilise le terme prime word.
- ↑ Résultat attribué à Victor A. Ufnarovskij, « Combinatorial and asymptotic methods in algebra », dans Alexei Kostrikin et Igor Chafarevitch (éditeurs), Algebra VI : Combinatorial and Asymptotic Methods of Algebra. Non-Associative Structures, Berlin, Springer, coll. « Encyclopaedia Math. Sci. » (no 57), , x + 290 p. (ISBN 978-3-540-54699-3, zbMATH 0826.16001), p. 1–190.
- ↑ 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).
- ↑ Berstel, Pocchiola (1994).
- ↑ 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).
- ↑ Une description détaillée, avec justification, est donnée dans Lothaire (2005)
- ↑ Reutenauer (1993) décrit l'algèbre de mélange en détail.
- ↑ Voir Kufleitner (2009).
- ↑ 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).
- ↑ La définition, et la factorisation décroissante, sont de Siromoney et. al. (1994)
- ↑ Cet exemple est de Melançon (2000).
- ↑ Cette terminologie est introduite dans Richomme (2003).
- ↑ Jean Berstel et Luc Boasson, « The set of Lyndon words is not context-free », Bulletin of the European Association for Theoretical Computer Science 63 (1997), vol. 63, no 1, , p. 139-140.
- ↑ Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, , 520 p. (ISBN 978-981-4271-66-0, présentation en ligne)
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lyndon word » (voir la liste des auteurs).
Bibliographie
- Jean Berstel et Dominique Perrin (2007), « The origins of combinatorics on words », European Journal of Combinatorics, vol. 28, no 3, , p. 996–1022 (DOI 10.1016/j.ejc.2005.07.019, MR 2300777, 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, nos 1-2, , p. 415–425 (DOI 10.1016/0304-3975(94)00013-1, MR 1290554, 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, , p. 2239–2246 (DOI 10.1016/j.patcog.2008.11.010, 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, , p. 81–95 (DOI 10.2307/1970044, MR 0102539)
- Francesco Dolce, Antonio Restivo et Christophe Reutenauer (2019), « Some Variations on Lyndon Words (Invited Talk) », dans Nadia Pisanti et Solon P. Pissis (éditeurs), 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), Dagstuhl, Germany, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (no 128), (ISBN 978-3-95977-103-0, DOI 10.4230/LIPIcs.CPM.2019.2, lire en ligne), p. 2:1-2:14
- Francesco Dolce, Antonio Restivo et Christophe (2019) Reutenauer, « On generalized Lyndon words », Theoretical Computer Science, vol. 777, , p. 232–242 (DOI 10.1016/j.tcs.2018.12.015).
- Jean-Pierre Duval (1983), « Factorizing words over an ordered alphabet », Journal of Algorithms, vol. 4, no 4, , p. 363–381 (DOI 10.1016/0196-6774(83)90017-2) 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, , p. 255–283 (DOI 10.1016/0304-3975(88)90113-2, MR 979464) 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, , p. 207–210 (DOI 10.1016/0012-365X(78)90002-X, MR 523071) 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, (MR 0248115), p. 358--370 lien Math Reviews
- Donald E. Knuth (2011), The Art of Computer Programming, vol. 4A : Combinatorial Algorithms, Part 1, Addison-Wesley, (ISBN 978-0-201-03804-0 et 0-201-03804-8, présentation en ligne)
- Manfred Kufleitner (2009), « On bijective variants of the Burrows-Wheeler transform », dans Jan Holub et Jan Žďárek (éditeurs), Prague Stringology Conference, (arXiv 0908.0239, 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), (ISBN 978-0-201-13516-9, présentation en ligne) 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), (ISBN 978-0-521-84802-2, présentation en ligne)
- Roger C. Lyndon (1954), « On Burnside's problem », Transactions of the American Mathematical Society, vol. 77, , p. 202–215 (MR 0064049) lien Math Reviews
- Monroe H. Martin (1934), « A problem in arrangements », Bulletin of the American Mathematical Society, vol. 40, no 12, , p. 859–864 (DOI 10.1090/S0002-9904-1934-05988-3, MR 1562989) lien Math Reviews
- (en) Guy Melançon (2000), « Lyndon factorization of Sturmian words », Discrete Mathematics, vol. 210, nos 1-3, , p. 137--149 (MR 2001c:68107) 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, , p. 432–454 (MR 0540649) lien Math Reviews
- Christophe Reutenauer (1993), Free Lie algebras, The Clarendon Press Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (no 7), (ISBN 978-0-19-853679-6, MR 1231799, présentation en ligne) lien Math Reviews
- Christophe Reutenauer (2006), « Mots de Lyndon généralisés », Séminaire lotharingien de combinatoire, vol. 54, , article no B54h (lire en ligne).
- Gwénaël Richomme (2003), « Lyndon morphisms », Bulletin of the Belgian mathematical society Simon Stevin, vol. 10, , p. 761-785 (MR 2005d:68116) lien Math Reviews
- Rani Siromoney, Lisa Mathew, V. R. Dare et K. G. Subramanian (1994), « Infinite Lyndon words », Information Processing Letters, vol. 50, , p. 101-104
- Marcel-Paul Schützenberger (1965), « On a factorisation of free monoids », Proceedings of the American Mathematical Society, vol. 16, , p. 21–24 (MR 0170971) lien Math Reviews
Articles liés
Liens externes
- (en) Guy Melançon, « Lyndon word », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne)
- (en) Frank Ruskey (2003), Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences
Portail des mathématiques