Combinatoire des mots

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é

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

La fonction de complexité 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 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 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.

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

Références

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Combinatoire des mots de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Combinatoire — Pour les articles homonymes, voir combinatoire (homonymie). Une planche de l encyclopédie de Diderot et d Alembert illustrant l article « Carreleur » …   Wikipédia en Français

  • Combinatoire Sémantique — La combinatoire sémantique est la recherche du sens total d’un énoncé par « calcul » à partir de ses unités constituantes. Sommaire 1 Support de la combinatoire sémantique 1.1 Syntaxe et sémantique 1.2 Unités sémantiques …   Wikipédia en Français

  • Combinatoire semantique — Combinatoire sémantique La combinatoire sémantique est la recherche du sens total d’un énoncé par « calcul » à partir de ses unités constituantes. Sommaire 1 Support de la combinatoire sémantique 1.1 Syntaxe et sémantique 1.2 Unités… …   Wikipédia en Français

  • combinatoire — [ kɔ̃binatwar ] adj. et n. f. • 1732 philos.; de combiner 1 ♦ (1819) Relatif aux combinaisons, à leur dénombrement et leur mise en ordre; qui procède par combinaison d éléments. Math. Analyse combinatoire : théorie des ensembles finis traitant du …   Encyclopédie Universelle

  • Des chiffres et des lettres — Titre original Le Mot le plus long Genre Jeu télévisé Création Arman …   Wikipédia en Français

  • Combinatoire sémantique — La combinatoire sémantique est la recherche du sens total d’un énoncé par « calcul » à partir de ses unités constituantes. Sommaire 1 Support de la combinatoire sémantique 1.1 Syntaxe et sémantique 1.2 Unités sémantiques …   Wikipédia en Français

  • Mots de Lyndon — En mathématiques, dans les domaines de la combinatoire et de l informatique, un mot de Lyndon est un certain type de mot sur un alphabet. Il existe différentes définitions équivalentes. Un mot de Lyndon k aire de longueur n est un mot à n lettres …   Wikipédia en Français

  • Combinatoire algébrique — En mathématiques, la combinatoire algébrique est une discipline qui traite de l étude des structures algébriques par des techniques algorithmiques et combinatoires. Sommaire 1 Principe 2 Théorie des groupes 2.1 Groupes …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Des Chiffres Et Des Lettres — Genre Jeu télévisé Présenté par Patrice Laffont (1972 1989) Laurent Cabrol (1989 1992) Max Meynier …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”