DOI

Given an infinite word x = x0x1x2 ···∈AN over some finite alpha-bet 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 aconcatenation 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.

Original languageEnglish
Pages (from-to)3103-3115
Number of pages13
JournalProceedings of the American Mathematical Society
Volume147
Issue number7
DOIs
StatePublished - Jul 2019

    Scopus subject areas

  • Applied Mathematics
  • Mathematics(all)

    Research areas

  • Factor complexity, Linear complexity, Sturmian words, linear complexity

ID: 41185889