Mots de Lyndon

En mathématiques, dans les domaines de la combinatoire et de l'informatique, un mot de Lyndon est un certain type de mot sur un alphabet. Il existe différentes définitions équivalentes.

Un mot de Lyndon k-aire de longueur n est un mot à n lettres sur un alphabet de taille k, et qui est strictement minimal (au sens de l'ordre lexicographique) parmi tous ses 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 apériodique.

Alternativement, un mot de Lyndon possède la propriété suivante : si on le scinde en deux mots, il est toujours lexicographiquement plus petit que son suffixe. C'est-à-dire que si w est un mot de Lyndon et que w = uv est une factorisation en deux sous-mots, avec u et v non vides, alors w < v. Cette définition implique que w est un mot de Lyndon si et seulement s'il existe deux mots u et v tels que u < v et w = uv. Cette propriété permet de générer récursivement tous les mots de Lyndon, d'où son importance en informatique.

Les mots de Lyndon correspondent à une classe de représentants de colliers apériodiques et peuvent donc être dénombrés par la fonction de Moreau des colliers.

Les mots de Lyndon ont une application dans la description des algèbres de Lie libre car ils permettent de construire une base pour la partie homogène de degré fixé. Les mots de Lyndon peuvent vus comme un cas spécial d'ensemble de Hall.

Le théorème de Radford affirme que l' algèbre des polynômes des mots de Lyndon avec des coefficients rationnels est une algèbre de mélange ; c'est-à-dire, ils forment une algèbre sur un anneau, en considérant le produit de mélange comme multiplication.

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

Références

• (en) « Lyndon word », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2001 (ISBN 978-155608010-4) [lire en ligne] 
• Frank Ruskey, Info on necklaces, Lyndon words, De Bruijn sequences, (2003)

Voir aussi

• De Bruijn sequence