Keywords :
k-binomial equivalence; k-binomial complexity; binomial coefficients on words; combinatorics on words; equivalence relations; complexity functions; factor complexity; growth order; nil-2 group; reconstruction problem for words; combinatoire des mots; relations d'équivalence; équivalence k-binomiale; fonctions de complexité; complexité factorielle; complexité k-binomiale; ordre de croissance; nil-2 groupe; problème de reconstruction des mots
Abstract :
[en] Complexity functions are well-studied objects in combinatorics on words. They encode some information about an infinite word: they count, for every non-negative integer n, the number of factors of length n present in the infinite word. One may take variations of the classical factor complexity, by counting not all factors, but only those which are different enough one from the other. To this aim one can define an equivalence relation and count, for any n, the number of equivalence classes among all factors of length n of a given infinite word. In this thesis we are interested into the k-binomial equivalence and its associated complexity. This latter equivalence involves the notion of binomial coefficient of words, counting, given two words u and x, the number of times (u,x) that x appears in u as a subword. Two words u and v are k-binomially equivalent if (u,x)= (v,x) for every word x of length up to k. In this manuscript we first count the number of k-binomial equivalence classes and give an algorithm generating the 2-binomial class of a finite word. We also show that the monoid A^* / ~2 is isomorphic to the submonoid, generated by A , of the nil-2 group N_2 (A) . We then compute the exact values of the k-binomial complexity of the Thue–Morse word and the Tribonacci word, and we discuss the techniques employed, in
an aim of generalizing it to larger families of words. Finally, we study a variant of the classical reconstruction problem and show that, proceeding in a sequential way, knowing n/2 + 1 well-chosen binomial coefficients is sufficient for reconstructing any binary word of length n. We also treat the case of an arbitrary alphabet and show that our bounds are better than what was known in the classical reconstruction case.
[fr] Les fonctions de complexité sont des objets souvent étudiés en combinatoire des mots. Elles permettent d’encoder beaucoup d’information sur un mot infini : elles comptent, pour chaque naturel n, le nombre de facteurs de longueur n qui apparaissent dans le mot infini. Il est possible de considérer des variations de la complexité factorielle classique en comptant non pas tous les facteurs, mais seulement ceux qui sont assez différents les uns des autres. C’est dans ce but que nous présentons une relation d’équivalence et comptons, pour chaque n, le nombre de classes d’équivalence parmi les facteurs de longueur n du mot infini donné. Dans cette thèse, nous nous intéressons à la relation d’équivalence k-binomiale et à sa fonction de complexité associée.
Ces dernières font intervenir la notion de coefficient binomial de deux mots, comptant, étant donnés deux mots u et x, le nombre (u,x) de fois que le mot x apparait comme sous-mot dans u. Deux mots u et v sont alors dits k-binomialement équivalents si (u,x) = (v,x) pour tous les mots x de longueur au plus k. Dans ce manuscrit, nous commençons par compter le nombre de classes d’équivalence k-binomiale et donnons un algorithme permettant de générer la classe 2-binomiale d’un mot fini donné. Nous montrons aussi que le monoïde A^* / ~2 est isomorphe au sous-monoïde, généré par
A , du nil-2 groupe N_2 (A) . Nous calculons ensuite les valeurs exactes des fonctions de complexité k-binomiale des mots de Thue–Morse et Tribonacci. Nous discutons des techniques employées dans le but de les généraliser afin de permettre l’étude de la complexité k-binomiale sur des familles plus larges de mots infinis. Enfin, nous étudions une variation du problème de reconstruction de mots. Nous montrons que, en procédant de façon séquentielle, il est possible de reconstruire n’importe quel mot binaire de longueur n en connaissant seulement n/2 + 1 coefficients binomiaux bien
choisis. Nous traitons aussi le cas d’un alphabet quelconque et montrons que nos bornes sont meilleures que celles connues dans le cas du problème de reconstruction classique.
