zbMATH — the first resource for mathematics

Rank and symbolic complexity. (English) Zbl 0858.68051
Summary: We investigate the relation between the complexity function of a sequence, that is the number \(p(n)\) of its factors of length \(n\), and the rank of the associated dynamical system, that is the number of Rokhlin towers required to approximate it. We prove that if the rank is one, then \(\liminf_{n\to+\infty}p(n)/n^2\leq{1\over 2}\), but give examples with \(\limsup_{n\to+\infty}p(n)/G(n)=1\) for any prescribed function \(G\) with \(G(n) = o(a^n)\) for every \(a>I\). We give exact computations for examples of the ‘staircase’ type, which are strongly mixing systems with quadratic complexity. Conversely, for minimal sequences, if \(p(n)<an + b\) for some \(a\geq1\), the rank is at most \(2[a]\), with bounded strings of spacers, and the system is generated by a finite number of substitutions.

68Q45 Formal languages and automata
Full Text: DOI
[1] Arnoux, Bull. Soc. Math. 119 pp 199– (1991)
[2] Queffelec, Lecture Notes in Mathematics 1294 (1987)
[3] Ornstein, Mem. Am. Math. Soc. 262 pp none– (1982)
[4] Ornstein, Proc. Sixth Berkeley Symp. on Mathematical Statistics and Probability pp 347– (1970)
[5] DOI: 10.2307/2371264 · Zbl 0019.33502 · doi:10.2307/2371264
[6] Chacon, Proc. Fifth Berkeley Symp. on Mathematical Statistics and Probability pp 335– (1965)
[7] Ferenczi, Bull. Soc. Math. 123 pp 271– (1995)
[8] DOI: 10.2307/2371449 · Zbl 0024.41702 · doi:10.2307/2371449
[9] del Junco, Canadian J. Math. 24 pp 836– (1976) · Zbl 0312.47003 · doi:10.4153/CJM-1976-080-3
[10] DOI: 10.1007/BF01706087 · Zbl 0253.02029 · doi:10.1007/BF01706087
[11] Kalikow, Ergod. Th. & Dynam. Sys. 4 pp 237– (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.