Combinatoire des mots

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Construction de la suite de Prouhet-Thue-Morse.

La combinatoire des mots est une branche des mathématiques et de l'informatique théorique qui applique l'analyse combinatoire aux mots finis ou infinis. Cette branche s'est développée à partir de plusieurs branches des mathématiques : la théorie des nombres, la théorie des groupes, les probabilités et bien sûr la combinatoire. Elle a des liens avec divers thèmes informatiques, comme l'algorithmique du texte (en), la recherche de motifs, la compression de textes.

Définition[modifier | modifier le code]

La combinatoire des mots a pour objet d'étude les propriétés de mots finis ou mots infinis particuliers. Ceci est à comparer à la théorie des langages formels, qui s'intéresse aux ensembles de mots, en vue de leur représentation et leur analyse.

Pour une classe de mots, l'étude porte sur les caractérisations équivalentes, les propriétés combinatoires, le dénombrement, l'énumération systématique ou la génération aléatoire. On étudie aussi les algorithmes et leur efficacité pour la réalisation effective de ces opérations.

Applications[modifier | modifier le code]

La combinatoire des mots a des applications dans des domaines variés de l'informatique théorique, comme la théorie des automates et de la linguistique. Le développement du texte numérique et du traitement de texte a amené à d'importants développements de la combinatoire des mots. Elle est présente à la base de l'algorithmique du texte, du traitement automatique du langage naturel, du traitement de la parole et du bio-informatique.

Historique[modifier | modifier le code]

La combinatoire des mots remonte aux travaux d'Axel Thue sur les suites non-répétitives de symboles, au début du XXe siècle. Les principaux travaux, dans les années qui ont suivi, sont ceux de Marston Morse et de ses coauteurs sur la suite de Prouhet-Thue-Morse et les mots sturmiens. Une célèbre application de la combinatoire des mots est l'usage qui est fait d'une suite sans répétition dans la réponse négative à la conjecture de Burnside apportée par Pyotr Novikov (en) et Sergei Adjan (en).

C'est Marcel-Paul Schützenberger qui est le fondateur de la combinatoire des mots moderne. À partir de notes préparées par Jean-François Perrot, est issu le livre "Combinatorics on words", ouvrage collectif signé du nom de plume M. Lothaire, et paru en 1983. La combinatoire des mots se développa rapidement à partir de cette date.

Les principaux thèmes[modifier | modifier le code]

Mots de Lyndon[modifier | modifier le code]

Article détaillé : mot de Lyndon.

Les mots de Lyndon, nommés ainsi d'après le mathématicien Roger Lyndon, sont les mots primitifs et minimaux dans leur classe de conjugaison. L'un des résultats de base est que tout mot admet une factorisation décroissante unique en mots de Lyndon (résultat attribué par erreur à Chen, Fox et Lyndon). Un autre résultat remarquable est que le produit, en ordre croissant, des mots de Lyndon dont la longueur divise un entier donné est un mot de de Bruijn.

Mots sans répétition[modifier | modifier le code]

Articles détaillés : mot sans carré et motif inévitable.

La combinatoire des mots s'est notamment attachée à décrire les conditions dans lesquelles les répétitions apparaissent dans les mots (mots sans carré, entre autres), la construction ou la transformation des mots, par morphisme. Un cas plus général est couvert par la notion de motif inévitable ou son contraire, les motifs évitables. Par exemple, le « motif » xyxyx (où x et y sont des symboles) dénote la présence, dans un mot, d'un facteur de la forme uvuvu (où cette fois-ci, u et v sont des mots). Dire qu'un mot évite ce motif, c'est qu'il ne contient pas ce facteur. Dire qu'un motif est inévitable, c'est affirmer que tout mot assez long contient un facteur de la forme décrite par le motif. Le motif xyx est inévitable, le motif xyxyx est évitable, même sur deux lettres.

Mots de faible complexité[modifier | modifier le code]

Le mot de Fibonacci, caractérisé par une droite de pente \varphi ou \varphi-1 avec \varphi, le nombre d'or

La fonction de complexité[1] d'un mot fini ou infini x est la fonction n\mapsto c_x(n) qui, pour chaque entier n, compte le nombre de facteurs c_x(n)(ou blocs) de longueur n dans ce mot. Pour un mot infini x, un résultat dû à Ethan M. Coven et Gustav Hedlund dit que si c_x(n)\le n pour un entier n, alors le mot x est ultimement périodique. Les mots infinis apériodiques de complexité minimale ont donc une fonction de complexité égale à n+1. Ce sont les mots sturmiens. Le plus connu des mots sturmiens est le mot de Fibonacci.

Article détaillé : mot de faible complexité.

Mots automatiques[modifier | modifier le code]

Article détaillé : suite automatique.

Les mots automatiques sont des suites que l'on peut définir à l'aide d'automates finis. La suite de Prouhet-Thue-Morse est l'exemple paradigmatique de cette famille. Les pliages de papiers en sont un autre exemple.

Mots morphiques[modifier | modifier le code]

Article détaillé : mot morphique.

Un mot morphique est un mot infini obtenu par itération d'un morphisme, suivi de l'application d'un deuxième morphisme. En absence du deuxième morphisme, on parle de mot purement morphique. C'est une méthode très efficace et répandue de construction de mots infinie. Elle est « robuste » en ce sens qu'elle est stable par toute sorte d'opérations. Par exemple, le mot de Fibonacci infini est un mot purement morphique, la suite de Prouhet-Thue-Morse également. La suite caractéristique des carrés : 11001000010000001000... est morphique, mais n'est pas purement morphique.

Equations entre mots[modifier | modifier le code]

Un algorithme de calcul des solutions d'un ensemble fini d'équations entre mots a été donné par Makanin.

Définitions et propriétés diverses[modifier | modifier le code]

Récurrence[modifier | modifier le code]

Un mot infini x est récurrent si tout facteur de x apparaît une infinité de fois dans x.

  • Le mot ab^\omega n'est pas récurrent.
  • Le mot de Champernowne binaire 0100011011000001010011\ldots formé de la concaténation des développements binaires des entiers naturels est récurrent.
  • Un mot ultimement périodique et récurrent est périodique.

Un mot infini x est uniformément récurrent ou à lacunes bornées si deux occurrences consécutives d'un facteur de x sont à distance bornée. Plus précisément, pour tout facteur u de x, il existe une constante N(u) telle que deux occurrences consécutives de u dans x sont à distance au plus N(u).

  • Le mot de Champernowne binaire n'est pas uniformément récurrent. En effet, deux occurrences consécutives du symbole 1 peuvent être séparées par des séquences arbitrairement longues de 0.
  • Le mot de Fibonacci 01001010 01001 01001010\ldots est uniformément récurrent. Par exemple, les occurrences du chiffre 1 dans ce mot infini sont les éléments de la suite A001950 de l'OEIS, soit 2, 5, 7, 10, 13, 15, 18,... La distance entre deux 1 consécutifs est donc au plus 3.
  • Le mot de Thue-Morse est uniformément récurrent.

Il y a un lien entre les mots uniformément récurrents et les ensembles syndétiques. Un ensemble S d'entiers naturels est appelé syndétique s'il existe un entier N tel que pour deux entiers consécutifs s<t de S, on ait t-s<N. Un mot infini x est donc uniformément récurrent si, pour tout facteur u de x, l'ensemble S(u) des débuts d'occurrence de u dans x est syndétique.

La fonction de récurrence R d'un mot infini x donne la valeur maximale des lacunes entre occurrences consécutives de mots d'une longueur donnée. Plus précisément, R(n) est le plus petit entier N tel que tout facteur de x de longueur n soit facteur de tout facteur de longueur N de x, formellement R(n)=\inf\{N\mid \forall w\in F_N(x), F_n(w)=F_n(x)\} On peut voir l'entier R(n) comme la largeur minimale d'une fenêtre que l'on glisse sur le mot x et qui a la propriété que tout facteur de longueur n figure toujours dans la section couverte par la fenêtre.

  • Pour le mot de Fibonacci, on a R(1)=3, et R(2)=6; en effet, le facteur 01010 du mot de Fibonacci ne contient pas le facteur 00, mais tout facteur de longueur 6 contient les trois facteurs 00,01,10 parce que 10101 n'est pas facteur du mot de Fibonacci.

Fonction de récurrence de la suite de Prouhet-Thue-Morse[modifier | modifier le code]

Pour le mot de Thue-Morse 01101001100101101001\ldots, on a R(1)=3 (tout facteur de longueur 3 contient un 0 et un 1) et R(2)=9 (le facteur 01011010 ne contient pas 11). En fait, la fonction de récurrence a été calculée par Morse et Hedlund, dès 1938[2]. Les premières valeurs sont données dans la table suivante :

Fonction de récurrence de la suite de Prouhet-Thue-Morse
n 1 2 3 4 5 6 7 8 9 10
R(n) 3 9 11 21 22 41 42 43 44 81

C'est la suite A179867 de l'OEIS. La formule de récurrence est toute simple : pour n\ge2, on a R(2n)=2R(n+1)-1 R(2n+1)=2R(n+1). Il en résulte la forme close suivante. Posons n=2^r+p, avec 2\le p \le 2^r+1. Une telle écriture est toujours possible pour n\ge3. Alors R(n)= 10 \cdot 2^r+p-1.

Fonction de récurrence du mot infini de Fibonacci[modifier | modifier le code]

Cette fonction de récurrence a une expression un peu moins simple, et elle est connue depuis l'article de Morse et Hedlund de 1940. On a R(n)=F_{N+1}+F_N+n-1N est l'entier tel que F_N \le n < F_{N+1}. Ici, les F_N sont les nombres de Fibonacci avec F_0=0, F_1=1.

Fonction de récurrence du mot infini de Fibonacci
n 1 2 3 4 5 6 7 8 9 10
R(n) 3 6 10 11 17 18 19 28 29 30

C'est la suite A183545 de l'OEIS. Cette formule s'étend à tous les mots sturmiens.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Combinatorics on words » (voir la liste des auteurs)

  1. Cette notion de complexité ne doit pas être confondue avec la complexité algorithmique ou la complexité de Kolmogorov. C'est la complexité « en facteurs », en anglais « subword complexity ».
  2. Allouche & Shallit (2003), pages 328-331, et Morse & Hedlund (1938), pages 834-839.

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Problème du mot

Bibliographie[modifier | modifier le code]