Sequence entropy and the maximal pattern complexity of infinite words (Q4781863)

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\)).