## 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$$).

### MSC:

 37B10 Symbolic dynamics 37B40 Topological entropy

### Keywords:

pattern complexity; pattern Sturmian words

Zbl 1014.37003
Full Text: