Mot de Lyndon

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

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

La suite des nombres ${\displaystyle M(2,n)}$ est

1, ${\displaystyle 2,1,2,3,6,9,18,30,56,99,186,335,\cdots }$

C'est la suite A001037 de l'OEIS.

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

${\displaystyle abcabcb}$ (par (1) puis (3))

${\displaystyle abcabcc}$ (par (3))

${\displaystyle abcac}$ (par (2) puis (3))

${\displaystyle abcacac}$ (par (1) puis (3))

Dans le cas le plus défavorable, la procédure pour le calcul du successeur de ${\displaystyle w}$ est en ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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).

Le mot ${\displaystyle x=0110100110010110}$ s'écrit

${\displaystyle x=011\ 01\ 0011\ 001011\ 0}$,

et on a ${\displaystyle 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 ${\displaystyle u}$ et ${\displaystyle v}$ tels que ${\displaystyle u<v}$, tant que c'est possible. Ainsi

${\displaystyle 0\ 1\ 1\ 0\ 1\ 0\ 0\ 1\to 01\ 1\ 01\ 0\ 01\to 011\ 01\ 001}$

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 ${\displaystyle w=0110100110010110}$ a comme préfixe le mot ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle w}$ un mot de longueur ${\displaystyle n}$.

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

Exemple

Pour le mot ${\displaystyle w=abbabaab}$, l'algorithme débute par

${\displaystyle {\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 ${\displaystyle m-k=3}$, soit ${\displaystyle x=abb}$. L'algorithme reprend avec le mot ${\displaystyle w=abaab}$. On obtient

${\displaystyle {\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 ${\displaystyle y=ab}$ qui est l'élément suivant de la factorisation. On termine pour ${\displaystyle w=aab}$ par

${\displaystyle {\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 ${\displaystyle (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.

On connaît assez bien les termes extrêmes d'une factorisation de Lyndon: Soit ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ la factorisation de Lyndon d'un mot ${\displaystyle w}$; alors

• ${\displaystyle x_{n}}$ est le plus petit suffixe de ${\displaystyle w}$ pour l’ordre lexicographique;
• ${\displaystyle x_{n}}$ est aussi le plus long suffixe de ${\displaystyle w}$ qui est un mot de Lyndon;
• ${\displaystyle x_{1}}$ est aussi le plus long préfixe de ${\displaystyle w}$ qui est un mot de Lyndon.

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 ${\displaystyle \gamma }$ qui associe à un mot de Lyndon ${\displaystyle v}$ un élément de la base comme suit:

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

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

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.

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.

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 ${\displaystyle k}$ lettres dont la longueur divise un entier donné ${\displaystyle n}$, on obtient un mot de de Bruijn, c'est-à-dire un mot de longueur ${\displaystyle k^{n}}$ qui, vu comme mot circulaire, contient les ${\displaystyle k^{n}}$ mots de longueur ${\displaystyle 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 ${\displaystyle n}$ sur ${\displaystyle 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

1. Le mot infini

${\displaystyle ab^{\omega }}$

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

2. Le mot infini

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a}$, le mot obtenu n'a plus que trois préfixes qui sont des mots de Lyndon, à savoir ${\displaystyle a,ab}$ et ${\displaystyle abb}$.

3. Soit ${\displaystyle f=0100101001001\ldots }$ le mot de Fibonacci, défini par ${\displaystyle f=\lim s_{n}}$ avec ${\displaystyle s_{-1}=1}$, ${\displaystyle s_{0}=0}$ et ${\displaystyle s_{n+1}=s_{n}s_{n-1}}$pour ${\displaystyle n\geqslant 0}$. Alors le mot ${\displaystyle 0f}$ est un mot de Lyndon. Le mot ${\displaystyle 1f}$ est strictement plus grand que tous ses suffixes. Le résultat s'étend à tout mot Sturmien caractéristique.

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.

Le mot de Fibonacci

${\displaystyle f=010010100100101001010\cdots }$

a la factorisation

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

où

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

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