Option Informatique en Spé MP et MP*
Devoir surveillé du 25 novembre 1997
Réécriture, mots infinis, évitabilité, tours de Hanoï



Présentation

Au début du vingtième siècle, le mathématicien Axel Thue écrivit plusieurs articles fondant deux secteurs de l'informatique théorique: les systèmes de réécriture, qui interviennent par exemple dans les grammaires formelles, les méthodes de démonstration automatique, les logiciels de calcul formel; et l'étude des régularités dans les mots infinis, laquelle trouve actuellement des applications en génétique moléculaire.

Les deux premières parties du problème, après quelques généralités, étudient la terminaison de plusieurs systèmes de réécriture très simples (dont l'un a fait l'objet d'une question d'oral à Cachan). On donne quelques notions sur les mots infinis, en particulier ceux qui sont obtenus par itération d'un morphisme. La cinquième partie présente la notion de propriété inévitable, et caractérise les alphabets sur lesquels la propriété être sans facteur carré est évitable. Enfin, la sixième partie montre que la suite des mouvements, dans la solution optimale du problème des tours de Hanoï, peut être décrite par l'itération d'un morphisme, et que cette suite ne contient aucun facteur carré. Ce dernier résultat a été établi en 1991 par Dan Astoorian et Jim Randall, alors étudiants en licence à l'université de Waterlooo au Canada.

Ce sujet a été soumis à la sagacité des étudiants le mardi 25 novembre 1997.