On the k-binomial equivalence of finite words and k-binomial complexity of infinite words
Marie Lejeune · Open Repository and Bibliography (University of Liège) · 2021
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.