Bifix codes, Combinatorics on Words and Symbolic Dynamical Systems

Codes bifixes, combinatoire des mots et systèmes dynamiques symboliques L'étude des ensembles de mots complexité linéaire joue un rôle très important dans la théorie de combinatoire des mots et dans la théorie des systèmes dynamiques symboliques. Cette famille d'ensembles comprend les ensembles de facteurs : d'un mot Sturmien ou d'un mot d'Arnoux-Rauzy, d'un codage d'échange d'intervalle, d'un point fixe d'un morphisme primitif, etc. L'enjeu principal de cette thèse est l'étude de systèmes dynamiques minimales, définis de façon équivalente comme ensembles factoriels de mots uniformément récurrents. Comme résultat principal nous considérons une hiérarchie naturelle de systèmes minimal contenante les ensembles neutres, les tree sets et les ensembles spéculaires. De plus, on va relier ces systèmes au groupe libre en utilisant les mots de retours et les bases de sous-groupes d'indice fini. L'on étude aussi les systèmes symboliques dynamiques engendrés par les échanges d'intervalle et les involutions linéaires, ce qui nous permet d'obtenir des exemples et des interprétations géométriques des familles d'ensembles que définis dans notre hiérarchie. L'un des principal outil utilisé ici est l'étude des extensions possibles d'un mot dans un ensemble, ce qui nous permet de déterminer des propriétés telles que la complexité factorielle. Dans ce manuscrit, nous définissons le graphe d'extension, un graphe non orienté associé à chaque mot w dans un ensemble S qui décrit les extensions possibles de w dans S à gauche et à droite. Dans cette thèse, nous présentons plusieurs classes d'ensembles de mots définis par les formes possibles que les graphes d'extensions des éléments dans l'ensemble peuvent avoir. L'une des conditions les plus faibles que nous allons étudier est la condition de neutralité: un mot w est neutre si le nombre de paires (a,b) de lettres telles que awb ∈ S est égal au nombre de lettres a tel que aw ∈ S plus le nombre de lettres b tel que wb ∈ S moins 1. Un ensemble tel que chaque mot non vide satisfait la condition de neutralité est appelé un ensemble neutre. Une condition plus forte est la condition de l'arbre: un mot w satisfait cette condition si son graphe d'extension est à la fois acyclique et connecté. Un ensemble est appelé un tree set si tout mot non vide satisfait cette condition. La famille de tree sets récurrents apparaît comme fermeture naturelle de deux familles d'ensembles très importants : les facteurs d'un mot d'Arnoux-Rauzy et les ensembles d'échange d'intervalle. Nous présentons également les ensembles spéculaires, une sous-famille remarquable de tree sets. Il s'agit également de sous-ensembles de groupes qui forment une généralisation naturelle des groupes libres. Ces ensembles de mots sont une généralisation abstraite des codages naturelles d'échanges d'intervalle et d'involutions linéaires. Pour chaque classe d'ensembles considéré dans cette thèse, nous montrons plusieurs résultats concernant les propriétés de fermeture (sous décodage maximale bifixe ou par rapport aux mots dérivés), la cardinalité des codes bifixes et les de mots de retour, la connexion entre mots de retour et bases du groupe libre, ainsi qu'entre les codes bifixes et les sous-groupes du groupe libre. Chacun de ces résultats est prouvé en utilisant les hypothèses les plus faibles possibles