Maximal pattern complexity of higher dimensional words
Maximal pattern complexity of higher dimensional words
复制标题
DOI：
10.1016/j.jcta.2009.07.002
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Yanhui Qu;H. Rao;Z. Wen;Yumei Xue
中科院分区：
文献类型：
--
作者：
Yanhui Qu;H. Rao;Z. Wen;Yumei Xue
本文研究了n维词的模式复杂度。我们证明了一个n-循环但不是n-周期的字的模式复杂度至少为2k，推广了[T. Kamae，H. Rao，Y. M.薛，二维词的最大模式复杂度，理论。计算。Sci. 359（1-3）（2006）15-27]。定义了词的解析方向，其拓扑性质在证明中起着至关重要的作用。据此定义了n维模式Sturmian词。证明了无理旋转词是模式Sturmian的。引入了一类新的高维词--简单Toeplitz词。我们表明，他们也是模式Sturmian词。
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, Y.-M. Xue, Maximal pattern complexity of two dimension words, Theoret. Comput. Sci. 359 (1–3) (2006) 15–27] 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.