On low-complexity bi-infinite words and their factors
Alex Heinis · Journal de Théorie des Nombres de Bordeaux · 2001
In this paper we study bi-infinite words on two letters. We say that such a word has stiffness k if the number of different subwords of length n equals n + k for all n sufficiently large. The word is called k -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most k . In the present paper we give a complete description of the class of bi-infinite words of stiffness k and show that the number of subwords of length n from this class has growth order n 3 . In the case k = 1 we give an exact formula. We also consider the class of k -balanced bi-infinite words. It is well-known that the number of subwords of length n from this class has growth order n 3 if k = 1 . In contrast, we show that the number is ≥ 2 n / 2 when k ≥ 2 .