Combinatoire des mots finis

INTRODUCTION AUX MOTS FINIS

Théorème 1.1 (Lyndon, Schutzenberger, 1962 [64]). Soient x et y des mots finis non vides. Les affirmations suivantes sont équivalentes.
1. L’égalité xy = yx est vérifiée.
2. Les mots x, y possèdent une racine commune z.
3. Il existe des entiers strictement positifs n, m tels que xn = ym.
Nous aurons souvent besoin de manipuler des mots finis, munissons-nous donc d’un lexique approprié. Si f, p, u et s sont des mots satisfaisant l’équation u = p f s, (1.8) .

nous disons que p est un préfixe de u, que s est un suffixe de u et que f est un facteur de u. Ce dernier terme provient d’une lecture algébrique de l’équation (1.8). Si p ̸= u (respectivement s ̸= u), nous disons que p est un préfixe propre (respectivement un suffixe propre) de u. La position de f dans u est l’entier |p| et nous disons que f couvre les positions |p| à |p|+|f|−1 (incluses). Deux facteurs se chevauchent s’ils couvrent au moins une position commune. Remarquons que les préfixes et les suffixes sont toujours des facteurs. Lorsqu’un facteur apparaît dans une position autre que préfixe ou suffixe, nous l’appelons un facteur interne. Les préfixes du mot (1.2), abcabcabcabc, sont ε a ab abc abca abcab abcabc abcabca abcabcab abcabcabc abcabcabca abcabcabcab abcabcabcabc et les suffixes du mot (1.4), ccabccabccabcca, sont ε a ca cca bcca abcca cabcca ccabcca bccabcca abccabcca cabccabcca ccabccabcca bccabccabcca abccabccabcca cabccabccabcca ccabccabccabcca.

Le mot (1.7), baabaabbabaabababaabaabaabbabababbaabbaba, comprend 666 facteurs différents ; nous laissons au lecteur le soin de les énumérer. Le facteur bab apparaît aux positions 15, 18, 20 et 22 de ce même mot, et les deux dernières occurrences se chevauchent car elles couvrent toutes les deux la position 22. Comme nous venons de le constater, un facteur f peut apparaître plusieurs fois dans u ; nous parlons alors des occurrences de f dans u. Par de multiples occurrences, f peut être à la fois préfixe, facteur interne et suffixe de u. Ainsi, le facteur abc apparaît en position préfixe, interne et suffixe dans le mot (1.2). Le mot vide apparaît à toutes les positions de tous les mots. Enfin, le mot u est à la fois un préfixe et un suffixe de u lui-même, mais non un facteur interne. Nous notons |u|f le nombre d’occurrences de f dans u. Par abus de notation, si u est un mot commençant par la lettre a, nous notons a −1u le mot u privé de sa première lettre. De la même façon, si u termine par la lettre a, nous notons ua−1 le mot u privé de sa dernière lettre. Forts de ce vocabulaire, nous pouvons poursuivre notre introduction à la combinatoire des mots. Il existe un algorithme efficace permettant de tester si un mot est primitif ou non.

Proposition 1.2 (Folklore). Un mot u est primitif si et seulement s’il n’est pas un facteur interne de u² . Démonstration. Procédons par contraposée et supposons qu’il existe des mots p, s non vides tels que u² = p u s. Observons que |u| = |p| + |s|. Comme p est un préfixe et s un suffixe de u, nous déduisons que u = ps. L’équation u² = pus se réécrit alors psps = pus

et, en simplifiant par p à gauche et par s à droite, nous déduisons que u = ps = sp. Par le théorème 1.1, les mots s et p sont tous deux puissances d’un même mot z. Alors u est également puissance de z, donc non primitif. Réciproquement, si u n’est pas primitif, alors u = vn pour un mot v non vide et un entier n supérieur ou égal à 2. Ainsi, u² = v2n et nous pouvons prendre p = v et s = v 2n−2 comme solution de l’équation u² = pus.

Pour tester la primitivité d’un mot u, il suffit de chercher une occurrence de u dans u². Cette opération s’effectue en temps linéaire [52]. De nombreuses opérations sur les chaînes de caractères, notamment de recherche de sous-chaînes et de compression, peuvent s’effectuer plus rapidement sur des entrées non primitives si l’on connaît la racine primitive : la combinatoire sert bien l’algorithmique.

Périodicité

Considérons à nouveau le mot (1.4), ccabccabccabcca. Bien que primitif, il possède une forte régularité. Si un mot w vérifie wi = wi+k

pour tous les entiers i tels que i, i + k ∈ {0, . . . , |w| − 1}, alors nous disons que k est une période de w. Nous parlerons parfois de la période pour désigner le préfixe w0w1w2 . . . wk−1. Un mot w possédant une période k ≤ |w|/2 est appelé périodique. Un tel mot peut s’écrire w = u nu′ ,

avec un entier n ≥ 2 et un préfixe u′ de u. Le mot (1.4) admet 4 (ou ccab) comme période et se décompose en (ccab) 3 cca. La propriété « être non primitif » implique « être périodique » : si w = un (pour u non vide et n ≥ 2) alors w admet u comme période avec u′ = ε dans l’équation (1.2). L’inverse n’est pas vrai : le mot (1.4) est périodique sans être une puissance. Le lemme suivant donne une écriture en équations utile lorsque nous rencontrons un facteur périodique dans nos raisonnements.

Lemme 1.3 (Voir [63, prop. 1.3.4]). Soient x, y et z des mots finis. L’égalité xy = yz est vérifiée si et seulement s’il existe des mots u, v non vides et un entier naturel k tels que x = uv y = (uv) ku z = vu.