A characterization of words of linear complexity
Julien Cassaigne, Anna E. Frid, Svetlana Puzynina, Luca Quardo Zamboni · Proceedings of the American Mathematical Society · 2018
Given an infinite word x = x 0 x 1 x 2 ⋯ ∈ A N x=x_0x_1x_2\cdots \in \mathbb {A}^\mathbb {N} over some finite alphabet A , \mathbb {A}, the factor complexity p x ( n ) p_x(n) counts the number of distinct factors of x x of each given length n , n, i.e., the number of distinct blocks x i x i + 1 ⋯ x i + n − 1 ∈ A n x_ix_{i+1}\cdots x_{i+n-1}\in \mathbb {A}^n occurring in x . x. The factor complexity provides a useful measure of the extent of randomness of x x : periodic words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. In this paper we obtain a new characterization of infinite words x x of sublinear complexity, namely we show that p x ( n ) =