Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 3103-3115 |
Число страниц | 13 |
Журнал | Proceedings of the American Mathematical Society |
Том | 147 |
Номер выпуска | 7 |
DOI | |
Состояние | Опубликовано - июл 2019 |
ID: 41185889