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.