For a finite alphabet A and a sequence x A^N, Kamae and Zamboni defined the maximal pattern complexity function p^*ₓ (n) as a natural generalization of usual word complexity. They defined a nonperiodic sequence x to be pattern Sturmian if it achieves the minimal growth rate p^*ₓ (n) = 2n, and asked the question of whether one could classify recurrent pattern Sturmian sequences. We answer their question by characterizing recurrent pattern Sturmian sequences as one of two known types: either a coding of an irrational circle rotation by two intervals, or an element of what we call a nearly simple Toeplitz subshift. We also show that nonrecurrent pattern Sturmian sequences are either very close to constant (such examples were given by Kamae and Zamboni) or a (nonrecurrent) coding of an irrational circle rotation by two intervals. Our main new technique is to use topological properties of the maximal equicontinuous factor (MEF) of the subshift generated by x. In this way, we prove a general structural result about sequences with non-superlinear maximal pattern complexity: they are either nonrecurrent or minimal with MEF either an odometer or the product of a circle with a finite cyclic group.
Le et al. (Tue,) studied this question.