- Combinatoire des mots
-
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, 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 ou 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 parte 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é
La fonction de complexité d'un mot fini ou infini x est la fonction
qui, pour chaque entier n, compte le nombre de facteurs cx(n)(ou blocs) de longueur n dans ce mot. Pour un mot infini x, un résultat dû à Ethan M. Coven et Gustav Hedlund (de) dit que si 
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.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.
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
Liens externes
Wikimedia Foundation. 2010.
