Maximal pattern complexity of two-dimensional words

The maximal pattern complexity of one-dimensional words has been studied in several papers [T. Kamae, L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory Dynam. Systems 22(4) (2002) 1191–1199; T. Kamae, L. Zamboni, Maximal pattern complexity for discrete systems, Ergodic Theory Dynam. Systems 22(4) (2002) 1201–1214; T. Kamae, H. Rao, Pattern Complexity over ℓ letters, E. Comb. J., to appear; T. Kamae, Y.M. Xue, Two dimensional word with 2k maximal pattern complexity, Osaka J. Math. 41(2) (2004) 257–265]. We study the maximal pattern complexity of two-dimensional words α. A two-dimensional version of the notion of strong recurrence is introduced. It is shown that if α is strongly recurrent, then either α is doubly periodic or . Accordingly, we define a two-dimensional pattern Sturmian word as a strongly recurrent word α with . Examples of pattern Sturmian words are given.