Research output: Contribution to journal › Article › peer-review
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 language | English |
---|---|
Pages (from-to) | 3103-3115 |
Number of pages | 13 |
Journal | Proceedings of the American Mathematical Society |
Volume | 147 |
Issue number | 7 |
DOIs | |
State | Published - Jul 2019 |
ID: 41185889