Sequence entropy and the maximal pattern complexity of infinite words

Abstract

For an infinite word \alpha=\alpha_0\alpha_1\alpha_2\dots , over a finite alphabet A , we define the maximal pattern complexity by p_\alpha^*(k)=\sup_\tau\sharp\{\alpha_{n+\tau(0)} \alpha_{n+\tau(1)}\dots\alpha_{n+\tau(k-1)}; n=0,1,2,\dots\} where the ‘sup’ is taken over all subsequences 0=\tau(0)<\tau(1)<\dots<\tau(k-1) of integers of length k . We prove that \alpha is eventually periodic if and only if p_\alpha^*(k)\le 2k-1 for some k . Infinite words \alpha , with p_\alpha^*(k)=2k for any k , are called pattern Sturmian words and are studied.