Iterated morphisms, combinatorics on words and symbolic dynamical systems

La thèse actuelle porte sur le thème de la combinatoire des mots et des systèmes dynamiques symboliques. Les systèmes dynamiques symboliques sont des objets permettant de coder les trajectoires de mots dans des systèmes dynamiques de transformations d’espaces topologiques. Parmi ces systèmes dynamiques, des exemples bien connus sont donnés par des mots sturmiens et par d'échange d’intervalles. Les mots sturmiens sont liés à des algorithmes de géométrie discrète et l’échange d’intervalles forme une classe intéressante de systèmes dynamiques. En outre, il convient de mentionner que certaines familles d'échanges fournissent des généralisations prometteuses de mots sturmiens. Le sujet principal de la thèse est la reconnaissabilité des mots générés par les morphismes primitifs. Le concept de reconnaissabilité des morphismes trouve son origine dans l’article de Martin [1] sous le terme de détermination. Host a utilisé ce terme pour la première fois dans son article sur la théorie ergodique des systèmes dynamiques [2]. La notion de reconnaissabilité est apparue après lintêrt manifesté par de nombreux scientifiques pour ses diverses applications théoriques dans divers domaines, de la combinatoire des mots à la dynamique symbolique. Une notion similaire est celle de la circularit. Les deux termes sont souvent, mais pas toujours utilisés comme synonymes. Ce manque de cohérence dans la littérature pourrait être source de confusion. À la connaissance de l’auteur, il n’y a pas encore d’étude qui rassemble ces définitions et prouve leur équivalence ou indique les différences qui existent entre elles. Une approche solide de ce sujet, utilisant une définition cohérente de la reconnaissabilité et de la circularité. La notion de reconnaissabilité associée à une technique utilisée dans [3] a été utilisée afin de démontrer la décidabilité de différentes propriétés de graphes d’extension (définis dans [18]) d’éléments d’un langage. Les familles d’ensembles peuvent être définies à partir des propriétés du graphe d’extension de leurs éléments, tels que les ensembles acycliques, les ensembles d’arbres, les ensembles neutres, etc. Plus précisément, pour un ensemble de mots S, on peut associer à chaque mot w ∈ S son extension graphique qui décrit les extensions gauche et droite possibles de w dans S. Nous montrons comment utiliser la reconnaissabilité pour fournir la décidabilité des graphes d’extension. En outre, la notion de reconnaissance est utilisée dans lobjet de semigroupes profinite. Nous décrivons la relation entre la reconnaissabilité des morphismes et les propriétés des semigroupes profinites libres [5].Bibliography[1] John C. Martin. Minimal flows arising from substitutions of non-constant length. Math. Systems Theory, 7:72–82, 1973.[2] B. Host. Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable. Ergodic Theory Dynam. Systems, 6(4):529–540, 1986.[3] Klouda, K. and Starosta, Š. "Characterization of circular D0L systems", arXiv preprint arXiv:1401.0038 (2013).[4] Berthé, V., De Felice, C., Dolce, F. et al. Monatsh Math (2015) 176: 521. https://doi.org/10.1007/s00605-014-0721-4[5]Kyriakoglou ,R., Perrin ,D. "Profinite semigroups", arXiv:1703.10088 (2017)The current thesis focuses on the topic of combinatorics on words and symbolic dynamical systems. The symbolic dynamical systems are objects for encoding word trajectories in dynamic systems of transformations in topological spaces. Among these dynamical systems, well-known examples are given by Sturmial words and by exchange of intervals. The Sturmian words are related to discrete geometry algorithms and the exchange of intervals form an interesting class of dynamical systems. Furthermore, it should be mentioned that some exchange families provide promising generalizations of Sturmian words.The main subject of the thesis is the recognizability of words generated by primitive morphisms. The concept of recognizability of morphisms originates in the paper of Martin [1] under the term of determinization. The term was first used by Host in his paper on the Ergodic theory of Dynamical Systems[2]. The notion of recognizability came in full bloom after the interest shown by many scientists due to its various theoretical applications in various topics, from combinatorics on words to symbolic dynamics. A similar notion is that of circularity. The two terms are often, but not always used as synonymous. This lack of consistency along the literature could result in confusion. To the best of the author’s knowledge, there is not, as of yet, any study that collects those definitions and proves their equivalence or indicates the differences among them. This thesis provides a solid approach to this subject, using a coherent definition of recognizability and circularity.The notion of recognizability alongside a technique used in [3] were used in order to prove the decidability of different properties of extension graphs (defined in [4]) of elements of a language. Families of sets can be defined from properties of the extension graph of their elements, such as acyclic sets, tree sets, neutral sets, etc. More precisely, given a set of words S, one can associate with every word w ∈ S it's extension graph which describes the possible left and right extensions of w in S. We show how to use the recognizability to provide decidability of extension graphs. Furthermore, recognizability is used in is the subject of Profinite Semigroups. We describe the relationship between the recognizability of morphisms and properties of the free profinite semigroups [5].Bibliography[1] John C. Martin. Minimal flows arising from substitutions of non-constant length. Math. Systems Theory, 7:72–82, 1973.[2] B. Host. Valeurs propres des systèmes dynamiques définis par des substitu-tions de longueur variable. Ergodic Theory Dynam. Systems, 6(4):529–540,1986.[3] Klouda, K. and Starosta, Š. "Characterization of circular D0L systems.", arXiv preprint arXiv:1401.0038 (2013).[4] Berthé, V., De Felice, C., Dolce, F. et al. Monatsh Math (2015) 176: 521. https://doi.org/10.1007/s00605-014-0721-4[5]Kyriakoglou ,R., Perrin ,D. "Profinite semigroups", arXiv:1703.10088 (2017)[6]Almeida, J., "Profinite semigroups and applications" In Structural theory of automata, semigroups, and universal algebra, volume 207 of NATO Sci.43 Ser. II Math. Phys. Chem., pages 1–45. Springer, Dordrecht, 2005. Notes taken by Alfredo Cost