Combinatoire des mots
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, la recherche de motifs, la compression de textes.
Sommaire |
Définition
La combinatoire des mots a pour objet d'étude les propriétés de mots finis 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
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
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 (en) 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
Mots de Lyndon
Les mots de Lyndon, nommés ainsi d'après le mathématicien Roger Lyndon (en), 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
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 facteur carré, entre autres), la construction ou la transformation des mots, par morphisme.
Mots de faible complexité
ou 
avec La fonction de complexité d'un mot fini ou infini 
est la fonction 
qui, pour chaque entier 
, compte le nombre de facteurs 
(ou blocs) de longueur dans ce mot. Pour un mot infini , un résultat dû à Ethan M. Coven et Gustav Hedlund dit que si 
pour un entier , alors le mot est ultimement périodique. Les mots infinis apériodiques de complexité minimale ont donc une fonction de complexité égale à 
. Ce sont les mots sturmiens. Le plus connu des mots sturmiens est le mot de Fibonacci.
Mots automatiques
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.
Equations entre mots
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
Récurrence
Un mot infini est récurrent si tout facteur de apparaît une infinité de fois dans .
- Le mot
n'est pas récurrent. - Le mot de Champernowne binaire
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.
n'est pas récurrent.
Un mot infini est uniformément récurrent ou à lacunes bornées si deux occurrences consécutives d'un facteur de sont à distance bornée. Plus précisément, pour tout facteur 
de , il existe une constante 
telle que deux occurrences consécutives de dans sont à distance au plus .
- Le mot de Champernowne binaire n'est pas uniformément récurrent. En effet, deux occurrences consécutives du symbole
peuvent être séparées par des séquences arbitrairement longues de 
. - Le mot de Fibonacci
est uniformément récurrent. Par exemple, les occurrences des dans le 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 consécutifs est donc au plus 3. - Le mot de Thue-Morse est uniformément récurrent.
peuvent être séparées par des séquences arbitrairement longues de 
.
Un ensemble 
d'entiers naturels est un ensemble syndétique s'il existe un entier 
tel que pour deux entiers consécutifs 
de , on ait 
. Un mot infini est donc uniformément récurrent si, pour tout facteur de , l'ensemble 
des débuts d'occurrence de dans est syndétique.
La fonction de récurrence 
d'un mot infini donne la valeur maximale des lacunes entre occurrences consécutives de mots d'une longueur donnée. Plus précisément, 
est le plus petit entier tel que tout facteur de de longueur soit facteur de tout facteur de longueur de , formellent
On peut voir l'entier comme la largeur minimale d'une fenêtre que l'on glisse sur le mot et qui a la propriété que tout facteur de longueur figure toujours dans la section couverte par la fenêtre.
- Pour le mot de Fibonacci, on a
, et 
; en effet, le facteur 
du mot de Fibonacci ne contient pas le facteur 
, mais tout facteur de longueur 6 contient les trois facteurs 
parce que 
n'est pas facteur du mot de Fibonacci. - Pour le mot de Thue-Morse
, on a (tout facteur de longueur 3 contient un et un ) et 
(le facteur 
ne contient pas 
).
, et 
; en effet, le facteur 
du mot de Fibonacci ne contient pas le facteur 
, mais tout facteur de longueur 6 contient les trois facteurs 
parce que 
n'est pas facteur du mot de Fibonacci.
, on a 
(le facteur 
ne contient pas 
).Voir aussi
- Langage formel
- Mot de Fibonacci
- Mot sans facteur carré
- Mot sturmien
- Suite de Prouhet-Thue-Morse
- Problème du mot
Références
- Les origines de la combinatoire des mots, Jean Berstel, Dominique Perrin, European Journal of Combinatorics 28 (2007) 996–1022
- Les débuts de la combinatoire des mots, séminaire EHESS, 2005.
- Combinatorics on words - a tutorial, Jean Berstel and Juhani Karhumäki. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 79:178-228, 2003.
- Combinatorics on Words: A New Challenging Topic, Juhani Karhumäki.
- Combinatorics of words, Christian Chorut, Juhani Karhumäki, in "Handbook of formal languages" volume 1, Grzegorz Rozenberg, Arto Salomaa, Springer, 1997, ISBN 978-3-540-60420-4.
- "Combinatorics on Words", M. Lothaire, Addison-Wesley, 1983, reprinted Cambridge University Press, 1997, ISBN 978-0-521-59924-5.
- "Algebraic Combinatorics on Words", M. Lothaire, Cambridge University Press, 2002, ISBN 978-0-521-81220-7.
- "Infinite words: automata, semigroups, logic and games", Dominique Perrin, Jean Éric Pin, Academic Press, 2004, ISBN 978-0-12-532111-2.
- "Applied Combinatorics on Words", M. Lothaire, Cambridge University Press, 2005, ISBN 978-0-521-84802-2.
- "Algorithmic Combinatorics on Partial Words", Francine Blanchet-Sadri, CRC Press, 2008, ISBN 978-1-4200-6092-8.
- "Combinatorics on Words: Christoffel Words and Repetitions in Words", Jean Berstel, Aaron Lauve, Christophe Reutenauer, Franco V. Saliola, American Mathematical Society and Centre de Recherches Mathématiques, 2008, ISBN 978-0-8218-4480-9.
- "Combinatorics of Compositions and Words", Silvia Heubach, Toufik Mansour, CRC Press, 2009, ISBN 978-1-4200-7267-9.
- "Word equations and related topics: 1st international workshop, IWWERT '90, Tübingen, Germany, October 1-3, 1990 : proceedings", Editor: Klaus Ulrich Schulz, Springer, 1992, ISBN 978-3-540-55124-9
- "Jewels of stringology: text algorithms", Maxime Crochemore, Wojciech Rytter, World Scientific, 2003, ISBN 978-981-02-4897-0
- "Combinatorics, Automata and Number Theory", Valérie Berthé, Michel Rigo, Cambridge University Press, 2010, ISBN 978-0-521-51597-9
