Contribution à l'étude de la complexité des suites substitutives

Abstract

Hedlund et Morse [1938] ont déterminé la formule de la fonction de récurrence pour la suite de Thue-Morse. L’objectif du premier chapitre de la thèse est de déterminer la fonction de récurrence pour d’autres suites points fixes de substitutions uniformes. Au chapitre 2, nous déterminons la fonction complexité pour les suites de Thue-Morse généralisées sur un alphabet à q lettres. Gottshalk et Heldlund [1964] ont caractérisé le langage du flot symbolique des suites bi-infinies de Thue-Morse. Au chapitre 3, nous donnons une description d’un langage L tel que le flot bilatéral du mot bi-infini de Rudin-Shapiro est l’ensemble de tous les mots bi-infinis ne contenant aucun mot de L. nous montrons que le flot unilatéral de Rudin-Shapiro est le seul flot minimal dont le langage ne contient aucun mot de L. Ces résultats s’étendent aux suites de Thue-Morse généralisées.