MP1/MP*: Option Informatique
Itération d'un morphisme alternant; le mot de Kolakoski



Présentation

Le mot de Kolakoski est l'unique mot infini sur l'alphabet {1,2} commençant par un 2 et égal à la suite des longueurs de ses blocs. On ne sait pas grand'chose de ce mot, à part le fait qu'il n'est pas ultimement périodique. Des conjectures sont ouvertes sur la répartition des 1 et des 2, sur la complexité.

  • La première partie présente, l'opérateur qui, à un mot u sur l'alphabet {1,2} ne contenant pas trois lettres consécutives identiques, associe la suite des longueurs de ses blocs, considérée comme un mot sur ce même alphabet.
  • La deuxième partie propose l'étude de l'itération de ce morphisme.
  • La troisième partie mène à la construction du mot de Kolakoski; on donne deux méthodes de calcul.