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 $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$ .
Une autre définition : $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 $u^{\omega }<w^{\omega }$ ^[3].
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

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 a la formule suivante, aussi appelée formule de Witt dans le contexte des algèbres de Lie :

M(k,n)={\frac {1}{n}}\sum _{d\,|\,n}\mu \left({\frac {n}{d}}\right)k^{d}

où $\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-kz}=\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^[4].

Exemple

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

1,

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

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.

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$ ).
Tant que le dernier symbole de $x$ est la plus grande lettre de l'alphabet, enlever cette lettre.
Remplacer la dernière lettre du mot $x$ par la lettre qui suit dans l'alphabet.

Exemple

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 longueur au plus $n$ 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 $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

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

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

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).
Soit $k$ l'indice de la lettre qui sert à la comparaison. Au début, $k=0$ .
Tant que $m<n$ $m<n$ , comparer $w[k]$ $w[k]$ et $w[m]$ $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$ .
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

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

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

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 $\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

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 $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 lexicographique, de tous les mots de de Bruijn de longueur $n$ sur $k$ 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 $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^[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

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)^{2}b(ab)^{3}b\cdots (ab)^{n}b\cdots

est un mot de Lyndon infini car chaque préfixe $a(ab)b(ab)^{2}b(ab)^{3}b\cdots (ab)^{n}b$ 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$ .

3. Soit $f=0100101001001\ldots$ le mot de Fibonacci, défini par $f=\lim s_{n}$ avec $s_{-1}=1$ , $s_{0}=0$ et $s_{n+1}=s_{n}s_{n-1}$ pour $n\geqslant 0$ . Alors le mot $0f$ est un mot de Lyndon. Le mot $1f$ 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 $x$ possède une factorisation unique de l'une des deux formes :

$x=z_{1}z_{2}\cdots z_{n}y$ , où $z_{1}\geq z_{2}\geq \cdots \geq z_{n}\geq y$ , $z_{1},z_{2},\ldots ,z_{n}$ sont des mots de Lyndon finis et $y$ est un mot de Lyndon infini;
$x=z_{1}z_{2}\cdots z_{n}\cdots$ , où $z_{1}\geq z_{2}\geq \cdots \geq z_{n}\geq \cdots$ , $z_{1},z_{2},\ldots ,z_{n},\ldots$ sont des mots de Lyndon.

Exemple

Le mot de Fibonacci

f=010010100100101001010\cdots

a la factorisation

f=z_{1}z_{2}z_{3}\cdots

où

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

et les mots $z_{n}$ sont des mots de Lyndon décroissants^[12].

Morphisme de Lyndon

Un morphisme $f:A^{\star }\to B^{\star }$ est un morphisme de Lyndon^[13] 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\leq y$ implique $f(x)\leq 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_{i}a_{n}^{k_{i}})<f(a_{i+1})$ , où $k_{i}$ est le plus petit entier tel que $|f(a_{i}a_{n}^{k_{i}})|\geq |f(a_{i+1}|$ .

Langage des mots de Lyndon

L'ensemble des mots de Lyndon sur un alphabet $A$ 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. » (n^o 57), 1995, 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, n^o 1,‎ 1997, p. 139-140.
↑ Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, 2014, 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, n^o 3,‎ 2007, 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, n^os 1-2,‎ 1994, 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, n^o 10,‎ 2009, 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, 2^e série, vol. 68, n^o 1,‎ 1958, 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) » (n^o 128), 2019 (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,‎ 2019, 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, n^o 4,‎ 1983, 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, n^o 3,‎ 1988, 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, n^o 3,‎ 1978, 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, 1969 (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, 2011 (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, 2009 (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 » (n^o 17), 1983 (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 » (n^o 105), 2005 (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,‎ 1954, p. 202–215 (MR 0064049) lien Math Reviews
Monroe H. Martin (1934), « A problem in arrangements », Bulletin of the American Mathematical Society, vol. 40, n^o 12,‎ 1934, 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, n^os 1-3,‎ 2000, 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, n^o 2,‎ 1979, 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 » (n^o 7), 1993 (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,‎ 2006, article n^o B54h (lire en ligne).
Gwénaël Richomme (2003), « Lyndon morphisms », Bulletin of the Belgian mathematical society Simon Stevin, vol. 10,‎ 2003, 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,‎ 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 (MR 0170971) lien Math Reviews

Articles liés

Liens externes

(en) Guy Melançon, « Lyndon word », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)
(en) Frank Ruskey (2003), Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences

Portail des mathématiques

[1] Lyndon (1954)

[2] Knuth (2011) utilise le terme prime word.

[3] 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. » (n^o 57), 1995, x + 290 p. (ISBN 978-3-540-54699-3, zbMATH 0826.16001), p. 1–190.

[4] 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).

[5] Berstel, Pocchiola (1994).

[6] 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).

[7] Une description détaillée, avec justification, est donnée dans Lothaire (2005)

[8] Reutenauer (1993) décrit l'algèbre de mélange en détail.

[9] Voir Kufleitner (2009).

[10] 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).

[11] La définition, et la factorisation décroissante, sont de Siromoney et. al. (1994)

[12] Cet exemple est de Melançon (2000).

[13] Cette terminologie est introduite dans Richomme (2003).

[14] 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, n^o 1,‎ 1997, p. 139-140.

[15] Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, 2014, 520 p. (ISBN 978-981-4271-66-0, présentation en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]