Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Combinatoire des mots
Résumé
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 et la compression de textes.
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.
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.
La combinatoire des mots remonte aux travaux d'Axel Thue sur les suites non-répétitives de symboles, au début du . 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 Piotr Novikov et Adian.
C'est Marcel-Paul Schützenberger qui est le fondateur de la combinatoire des mots moderne, notamment dans des travaux avec Roger C. Lyndon et André Lentin.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.