Module indispensable : aucun, mais le domaine de recherche étant théorique,
un intérêt préalable pour les modules du parcours ACR est conseillé.
Module conseillé : Combinatoire des mots (UMINR 328).
Soit A un alphabet ordonné (par exemple l'alphabet usuel muni de l'ordre habituel - a < b < c ... - appelé ordre lexicographique). Un mot infini w sur A est sans carré s'il ne contient pas de facteur de la forme uu (u mot sur A).
Le stage a pour base la recherche de la réponse à la question suivante : quel est le plus petit mot infini sans carré dans l'ordre lexicographique ? Puisqu'il n'existe pas de mot infini sans carré sur deux lettres, cette question n'a de sens que pour un alphabet à trois lettres.
Malgré la simplicité de son énoncé, ce problème est plutôt difficile (des idées nouvelles sont nécessaires) et une solution complète n'est pas forcément attendue.
Le premier travail qui pourrait être effectué est la réalisation d'un "état de l'art" précis sur le sujet. Plus précisément :
Quelques références sont données ci-dessous. Cependant, des idées originales seront les bienvenues.
Le point de départ est le papier suivant dans lequel le problème
est énoncé :
Extremal infinite overlap-free binary morphisms, Allouche, Currie, Shallit,
Electronic J. Combinatorics 5 (1), 1998.
Des références utiles peuvent être trouvées dans
les livres de Lothaire (voir le site web de Jean Berstel).
Regardez également les travaux de Crochemore sur les morphismes sans
carré et le papier suivant dans lequel les références 26
et 27 peuvent être utiles : http://io.uwinnipeg.ca/~currie/sheltonII.pdf