Maximal pattern complexity of two-dimensional words
Maximal pattern complexity of two-dimensional words
复制标题
DOI：
10.1016/j.tcs.2006.02.023
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
T. Kamae;H. Rao;Yumei Xue
中科院分区：
文献类型：
--
作者：
T. Kamae;H. Rao;Yumei Xue
一维词的最大模式复杂度在文献[T。卡梅湖，澳-地Zamboni，序列熵和无限词的最大模式复杂度，遍历理论动力学。Systems 22（4）（2002）1191-1199; T.卡梅湖陈文，离散系统的最大模式复杂性，遍历理论。Systems 22（4）（2002）1201-1214; T. Kamae，H. Rao，基于字母的模式复杂性，E。J·康伯，出现; T。Kamae，Y.M. Xue，具有2k最大模式复杂度的二维字，Osaka J.Math.41（2）（2004）257-265]。研究了二维词α的最大模式复杂度pα*（k）.一个二维版本的强递归的概念。证明了若α是强常返的，则要么α是双周期的，要么pα*（k）<$2k（k= 1，2，.）相应地，我们定义一个二维Sturmian词为强递归词α，pα*（k）=2k. Sturmian模式词的例子。
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 pα*(k) 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 pα*(k)⩾2k(k=1,2,…). Accordingly, we define a two-dimensional pattern Sturmian word as a strongly recurrent word α with pα*(k)=2k. Examples of pattern Sturmian words are given.