MP1/MP*: Option Informatique
Devoir surveillé du mardi 9 février 1999
Sous-mots, mélange de mots, le théorème de Higman



Présentation

À côté de la notion classique de facteur d'un mot (ce que les anglo-saxons appellent subword), existe aussi la notion de sous-mot (que les mêmes baptisent subsequence ou scattered subword). Un sous-mot u d'un mot v est obtenu en effaçant de v zéro, une ou plusieurs lettres, mais en laissant les autres dans leur ordre initial.

Dans une première partie, on étudie quelques propriétés de la relation d'ordre sur X* associée à cette notion de sous-mot. C'est aussi l'occasion de rencontrer quelques langages rationnels.

La deuxième partie propose de calculer le nombre de façons dont un mot u peut être obtenu comme sous-mot d'un mot v; on présente un algorithme de calcul de ce nombre par programmation dynamique.

Dans une troisième partie, on définit le mélange (en anglais: shuffle) de deux mots; cette notion est fortement reliée à celle de sous-mot.

Enfin la dernière partie établit un résultat classique dû à Higman: dans un ensemble infini de mots, il existe nécessairement au moins un couple (u,v) de mots tels que u soit sous-mot de v. Ce résultat relève donc de l'étude des régularités inévitables.

Ce texte a été soumis à la sagacité des étudiants le mardi 9 février 1999.