Sequence entropy and the maximal pattern complexity of infinite words. (English) Zbl 1014.37004

The authors introduce the maximal pattern complexity for an infinite word \(\alpha =\alpha_0\alpha_1 \alpha_2\dots\) over a finite alphabet \(A\): they define it as \[ p^*_\alpha(k)=\sup_\tau\{\alpha_{n+\tau(0)}\alpha_{n+\tau(1)}\dots \alpha_{n+\tau(k-1)},\;n\in\mathbb{N}\} \] where the supremum is taken over all the subsequences \(0 =\tau(0) <\tau(1) <\dots < \tau(k-1)\) of integers of length \(k\). They prove that an infinite word \(\alpha\) is eventually periodic if and only if there exists some integer \(k > 0\), such that \(p^*_\alpha(k)\leq 2-1\).
At the end of the paper, the authors study several examples where they can compute the maximal pattern complexity. Specially, they study pattern Sturmian words (infinite words \(\alpha\) with \(p^*_\alpha(k)= 2k\) for all \(k\)).


37B10 Symbolic dynamics
37B40 Topological entropy


Zbl 1014.37003
Full Text: DOI