Fonction de complexité en facteurs et un théorème de PANSIOT

Abstract

Le but de ce mémoire est d'étudier les principales propriétés de la fonction de complexité en facteurs et, plus particulièrement, un théorème de Pansiot. Ce résultat classique en combinatoire des mots décrit complètement la complexité en facteurs des mots purement morphiques.

La complexité en facteurs d'un mot infini u est la fonction qui compte le nombre de facteurs de longueur n apparaissant dans u. Un résultat de Morse et Hedlund démontre qu'un mot est ultimement périodique si et seulement si sa fonction de complexité en facteurs est bornée par une constante. En d'autres termes, ce théorème montre que les mots périodiques sont les seuls à avoir une fonction de complexité en Θ(1).

Soit A un alphabet fini. Un mot purement morphique est un point fixe d'un morphisme σ : A* → A* du monoïde libre A* tel qu'il existe une lettre a satisfaisant σ(a)=au où u est un mot non vide et |σ^n(a)| tend vers l'infini avec n. Par exemple, le célèbre mot de Thue-Morse abbabaabbaababba... est un mot purement morphique obtenu en itérant le morphisme σ: a → ab, b → ba. La fonction de complexité du mot de Thue-Morse n'est pas bornée. Vu que ce mot est automatique, sa fonction de complexité en facteurs est en O(n).

Le théorème de Pansiot montre que la fonction de complexité d'un mot purement morphique ne peut avoir que l'un des quatre comportement asymptotiques suivants: n, nlog(n), nlog(log(n)) ou n², si on exclut le cas des mots périodiques caractérisés par le théorème de Morse et Hedlund.

Dans ce mémoire, nous introduisons des notions et des outils classiques tels que les facteurs spéciaux et les graphes de Rauzy permettant de mieux appréhender la fonction de complexité d'un mot infini. Par exemple, les graphes de Rauzy peuvent être utilisés pour caractériser les mots Sturmiens, qui sont les mots infinis apériodiques ayant une fonction de complexité égale à n+1 pour tout n. Remarquons que, par le théorème de Morse et Hedlund, n+1 est la borne inférieure pour une fonction de complexité en facteurs d'un mot apériodique. Dans le dernier chapitre, le caractère Sturmien du mot de Fibonacci abaababaabaababaa..., qui est le point fixe du morphisme σ : a → ab, b → a, est démontré. La forme exacte de la fonction de complexité du mot de Thue-Morse est également connue et étudiée dans ce mémoire.

The main goal of my Master thesis is to study the properties of the factor complexity function and, more particularly, a Theorem of Pansiot. This classical result in combinatorics on words completely describes the factor complexity of pure morphic words.

The factor complexity of an infinite word u is the map that counts the number of factors of length n occurring in u. A result of Morse and Hedlund shows that a word is ultimately periodic if and only if its factor complexity is bounded by a constant. In other words, this theorem shows that periodic words are the only ones having a complexity in Θ(1).

Let A be a finite alphabet. A pure morphic word is a fixed point of a morphism σ : A* → A* of the free monoid A* such that there exists a letter a satifying σ(a)=au where u is a non-empty word and |σ^n(a)| tends to infinity with n. For instance, the celebrated Thue-Morse word abbabaabbaababba... is a pure morphic word obtained from the morphism σ: a → ab, b → ba. The factor complexity of the Thue-Morse word is unbounded. Since this word is automatic, its complexity is in O(n).

Pansiot's result shows that the growth order of a pure morphic word can only take four forms: n, nlog(n), nlog(log(n)) or n², if we excluded the case of periodic words settled by Morse-Hedlund's theorem.

In this Master thesis, I present a study of special factors and Rauzy graphs as tools for determining the factor complexity of an infinite word. For instance, Rauzy graphs can be used for characterizing Sturmian words, which are the aperiodic words of factor complexity n+1. Note that n+1 is the minimal possible bound for the complexity function among aperiodic words by the Morse-Hedlund theorem. In the last chapter, the Fibonacci word abaababaabaababaa..., which is the fixed point of the morphism σ : a → ab, b → a, is proved to be a pure morphic Sturmian word. The exact form of the factor complexity of the Thue-Morse word is also well-known and studied in this Master thesis.