Évènement

Le jury sera composé de :

La dynamique symbolique et la combinatoire des mots sont deux approches complémentaires pour évaluer la complexité des mots infinis, ces derniers étant souvent des versions discrètes de processus plus complexes. Cette thèse explore deux notions centrales pour décrire les mots infinis : la complexité des facteurs est la fonction qui compte les mots finis de chaque longueur, et la récurrence uniforme/minimalité est une propriété qui contrôle la répartition des occurrences de chaque facteur.

Les substitutions sont une des principales manières de générer des mots infinis et ont donné naissance à une théorie prolifique qui est au cœur de la dynamique symbolique. En nous intéressant d’abord au problème du calcul de la complexité d’une suite morphique donnée, nous présentons une revue des résultats de Pansiot et de Devyatov qui décrivent les classes de complexité possibles. Ensuite, en nous fondant sur la caractérisation des sous-shifts substitutifs minimaux donnée récemment par Shimomura, nous étudions à quel point un sous-shift peut être non-minimal. Pour cela nous caractérisons et comptons les composantes minimales de ces sous-shifts.
Au-delà du cadre substitutif, la suite de Oldenburger-Kolakoski pose des questions notoirement difficiles à propos de sa récurrence, de sa complexité et de ses fréquences. En considérant la généralisation que sont les suites lisses sur des alphabets de deux entiers, nous présentons nos contributions à deux problèmes sur ce sujet. En premier nous étudions la complexité du langage des mots lisses, dont la conjecture est qu’elle croît comme Θ(n^ρ) où ρ dépend de l’alphabet. Nous prouvons la borne inférieure dans le cas général et la borne supérieure quand les deux lettres sont des entiers pairs, et nous améliorons la borne supérieure quand les deux lettres sont des entiers impairs. En second nous étudions les suites lisses sur les alphabets pairs et impairs, qui ont l’avantage d’avoir une représentation S-adique. Nous prouvons que ces suites sont uniformément récurrents, et, avec des conditions sur l’alphabet, qu’ils ont une complexité linéaire et sont uniquement ergodiques.

Mots clés : Dynamique symbolique, combinatoire des mots, complexité des facteurs, minimalité, substitutions, mots lisses

Beyond the substitutive framework, the famous Oldenburger-Kolakoski sequence raises difficult questions about its recurrence, its factor complexity and its frequencies. By considering a generalization called smooth sequences over 2-integer alphabets, we present contributions to two connected problems. We first study the factor complexity of the language of smooth words, which is conjectured to grow like Θ(n^ρ) where ρ depends on the alphabet. We prove the lower bound in the general case and the upper bound when the two letters are even integers, and we improve the known upper bound when the two letters are odd integers. Then we study smooth sequences over even and odd alphabets, which happen to have an S-adic representation. We prove that these sequences are uniformly recurrent, and, under conditions on the alphabet, that they have linear factor complexity and are uniquely ergodic.

Keywords: Symbolic dynamics, combinatorics on words, factor complexity, minimality, substitutions, smooth word