MP/MP*: Option Informatique
Autour du mot infini 0101101110... (17/11/2004)

Face à un mot infini sur un alphabet à deux lettres, on peut se poser de nombreuses questions:

• quels sont les facteurs qui apparaissent une seule fois?
• parmi ceux-ci, quels sont les facteurs minimaux?
• quels sont les facteur récurrents, i.e. ceux qui apparaissent une infinité de fois?
• parmi ceux-ci, en existe-t-il qui sont uniformément récurrents, c'est-à-dire qui apparaissent au moins une fois dans chaque facteur de longueur N, pour un N assez grand?
• existe-t-il des facteurs spéciaux, i.e. qui admettent deux prolongements vers la droite?
• combien existe-t-il de facteurs de longueur n?

Le texte proposé n'est pas difficile; il gagnerait à être en partie repris, car il y a une certaine redondance entre les questions 2, 3 et 4.