A characterization of words of linear complexity

Abstract:

Given an infinite word $x=x_0x_1x_2\cdots \in \mathbb {A}^\mathbb {N}$ over some finite alphabet $\mathbb {A},$ the factor complexity $p_x(n)$ counts the number of distinct factors of $x$ of each given length $n,$ i.e., the number of distinct blocks $x_ix_{i+1}\cdots x_{i+n-1}\in \mathbb {A}^n$ occurring in $x.$ The factor complexity provides a useful measure of the extent of randomness of $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$ of sublinear complexity, namely we show that $p_x(n)=O(n)$ if and only if there exists a set $S\subseteq \mathbb {A}^*$ of bounded complexity (meaning $\limsup p_S(n)<+\infty )$ such that each factor $w$ of $x$ is a concatenation of two elements of $S,$ i.e., $w=uv$ with $u,v \in S.$ In the process we introduce the notions of marker words and marker sets which are both new and may be of independent interest. Marker sets defined by right special factors constitute the key tool needed to split each factor of an infinite word of linear complexity into two pieces.