Search

Given an infinite word x = x0x1x2 · · · ∈ AN over some finite alphabet A, the factor complexity px(n) counts the number of distinct factors of x of each given length n, i.e., the number of distinct blocks xixi+1 · · · xi+n−1 ∈ An 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 px(n) = O(n) if and only if there exists a set S ⊆ A∗ of bounded complexity (meaning lim sup pS(n) < +∞) such that each factor w of x is a concatenation of two elements of S, i.e., w = uv with u, v ∈ 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. [ABSTRACT FROM AUTHOR]

In this paper we give a broad unified framework via group actions for constructing complexity functions of infinite words x = x0x1x2 ⋯ ∈ Aℕ with values in a finite set A. Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. We consider infinite sequences of permutation groups w = (Gn)n≥1 with each Gn ⊆ Sn. Associated with every such sequence is a complexity function pw,x : ℕ → ℕ which counts, for each length n, the number of equivalence classes of factors of x of length n under the action of Gn on An given by g * (u1u2 ⋯ un) = ug-1(1)ug-1(2) ⋯ ug-1(n). Each choice of w = (Gn)n≥1 defines a unique complexity function which reflects a different combinatorial property of a given infinite word. For instance, an infinite word x has bounded Abelian complexity if and only if x is k-balanced for some positive integer k, while bounded cyclic complexity is equivalent to x being ultimately periodic. A celebrated result of G.A. Hedlund and M. Morse states that every aperiodic infinite word x ∈ Aℕ contains at least n + 1 distinct factors of each length n. Moreover x ∈ Aℕ has exactly n + 1 distinct factors of each length n if and only if x is a Sturmian word, i.e., binary, aperiodic and balanced. We prove that this characterisation of aperiodicity and Sturmian words extends to this general framework. [ABSTRACT FROM AUTHOR]