×

Maximal pattern complexity of higher dimensional words. (English) Zbl 1228.05020

Summary: This paper studies the pattern complexity of \(n\)-dimensional words. We show that an \(n\)-recurrent but not \(n\)-periodic word has pattern complexity at least \(2k\), which generalizes the result of [T. Kamae, H. Rao and Y.-M. Xue, “Maximal pattern complexity of two dimension words”, Theor. Comput. Sci. 359, No. 1–3, 15–27 (2006; Zbl 1099.68050)] on two-dimensional words. Analytic directions of a word are defined and its topological properties play a crucial role in the proof.Accordingly \(n\)-dimensional pattern Sturmian words are defined. Irrational rotation words are proved to be pattern Sturmian. A new class of higher dimensional words, the simple Toeplitz words, are introduced. We show that they are also pattern Sturmian words.

MSC:

05A05 Permutations, words, matrices
68R15 Combinatorics on words

Citations:

Zbl 1099.68050
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnoux, P.; Berthé, V.; Ito, S., Discrete planes, \(Z^2\)-actions, Jacobi-Perron algorithm and substitutions, Ann. Inst. Fourier (Grenoble), 52, 2, 305-349 (2002) · Zbl 1017.11006
[2] Berthé, V., Sequences of low complexity: Automatic and Sturmian sequences, (London Math. Soc. Lecture Note Ser., vol. 279 (2000), Cambridge Univ. Press), 1-34 · Zbl 0976.11014
[3] Berthé, V.; Vuillon, L., Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb., 6, 2, 121-138 (2001) · Zbl 1002.11026
[4] Cassaigne, J., Two dimensional sequences with complexity \(m n + 1\), J. Autom. Lang. Comb., 4, 153-170 (1999) · Zbl 0971.68123
[5] Gjini, N.; Kamae, T.; Tan, B.; Xue, Y.-M., Maximal pattern complexity for Toeplitz words, Ergodic Theory Dynam. Systems, 26, 1073-1086 (2006) · Zbl 1108.68095
[6] Kamae, T.; Rao, H.; Xue, Y.-M., Maximal pattern complexity of two dimension words, Theoret. Comput. Sci., 359, 1-3, 15-27 (2006) · Zbl 1099.68050
[7] Kamae, T.; Rao, H.; Tan, B.; Xue, Y.-M., Language structure of pattern Sturmian words, Discrete Math., 306, 1651-1668 (2006) · Zbl 1097.68111
[8] Kamae, T.; Xue, Y.-M., Two dimensional word with \(2k\) maximal pattern complexity, Osaka J. Math., 41, 257-265 (2004) · Zbl 1053.37004
[9] Kamae, T.; Zamboni, L., Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory Dynam. Systems, 22, 4, 1191-1199 (2002) · Zbl 1014.37004
[10] Kamae, T.; Zamboni, L., Maximal pattern complexity for discrete systems, Ergodic Theory Dynam. Systems, 22, 4, 1201-1214 (2002) · Zbl 1014.37003
[11] Morse, M.; Hedlund, G. A., Symbolic dynamics II: Sturmian sequence, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[12] Vuillon, L., Combinatoire des motifs d’une suite sturmienne bidimensionelle, Theoret. Comput. Sci., 209, 261-285 (1998) · Zbl 0913.68206
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.