On the character of words of sub-linear complexity

International audienceLet A * denote the free monoid generated by a finite nonempty set A. For each infinite word x = x 0 x 1x 2··· ∈ A ω , the factor complexity p x (n) counts the number of distinct blocks xi xi+1···xi+n−1of length n occurring in x. In other words, the factor complexity of x is the complexity of the language of its factors Fac x={xixi+1···xj|0≤i≤j}. Ourstarting point in this paper is the following characterisation of infinite words of sub-linear factor complexity obtained recently by the author together with J. Cassaigne, A. Frid and S. Puzynina: Let x∈Aω. Then px(n) =O(n) if and nly if Fac(x) ⊆S2for some S⊆A∗ with lim sup pS(n)<+∞. In other words, px(n)≤Cn for some constant C if and only if there exists a set S of bounded complexity such that every factor wofx can be factored as w=uv with u,v∈S. Given an infinite word x∈Aω, we define its character , denoted χ(x) , to be the least value for lim sup pS(n) over all languages S such that Fac x⊆S2. Clearly χ(x)∈[1, +∞] and it follows from the above characterisation that px(n) = O (n) if and only if χ (x)<+∞. We prove that χ(x) = 1 if and only if x is ultimately periodic and that χ(x) = 2 whenever xis a Sturmian word