Complexity of infinite sequences with zero entropy. (English) Zbl 1275.68112
The complexity function of an infinite word represents the number of patterns of each length appearing in it.
This article deals with infinite words whose complexity function is bounded by some subexponential \(f\) such that, for any \(n\) large enough, \(f(n+1)>f(n)\geq n+1\), \(f(2n)\leq f(n)^2\) and \(f(n+1)\leq f(1)f(n)\).
It gives lower and upper bounds of the same form \(q^\psi(n)\), with \(\psi(n)=o(n)\), for the number of patterns that appear in such infinite words.
Reviewer’s remark: Contrary to what the abstract suggests, it does not apply to any case of subexponential complexity.
This article deals with infinite words whose complexity function is bounded by some subexponential \(f\) such that, for any \(n\) large enough, \(f(n+1)>f(n)\geq n+1\), \(f(2n)\leq f(n)^2\) and \(f(n+1)\leq f(1)f(n)\).
It gives lower and upper bounds of the same form \(q^\psi(n)\), with \(\psi(n)=o(n)\), for the number of patterns that appear in such infinite words.
Reviewer’s remark: Contrary to what the abstract suggests, it does not apply to any case of subexponential complexity.
Reviewer: Pierre Guillon (Marseille)
MSC:
| 68R15 | Combinatorics on words |
| 37B10 | Symbolic dynamics |
| 11B85 | Automata sequences |
| 37B40 | Topological entropy |
