Sequence entropy and the maximal pattern complexity of infinite words
Sequence entropy and the maximal pattern complexity of infinite words
复制标题
DOI：
10.1017/s014338570200055x
复制
发表时间：
2002-08
影响因子：
0.9
通讯作者：
T. Kamae;L. Zamboni
中科院分区：
文献类型：
--
作者：
T. Kamae;L. Zamboni
对于一个在有限字母表\(A\)上的无限字\(\alpha = \alpha_0\alpha_1\alpha_2\cdots\)，我们通过\(p_\alpha^*(k)=\sup_\tau\sharp\{\alpha_{n+\tau(0)} \alpha_{n+\tau(1)}\cdots\alpha_{n+\tau(k - 1)}; n = 0,1,2,\cdots\}\)来定义最大模式复杂度，其中“\(\sup\)”是对所有长度为\(k\)的整数子序列\(0 = \tau(0) < \tau(1) < \cdots < \tau(k - 1)\)取上确界。我们证明了\(\alpha\)最终是周期的当且仅当对于某个\(k\)，\(p_\alpha^*(k)\leq 2k - 1\)。对于任何\(k\)都有\(p_\alpha^*(k)=2k\)的无限字\(\alpha\)被称为模式斯图姆字并且被研究。
For an infinite word \alpha=\alpha_0\alpha_1\alpha_2\dots, over a finite alphabet A, we define the maximal pattern complexity by p_\alpha^*(k)=\sup_\tau\sharp\{\alpha_{n+\tau(0)} \alpha_{n+\tau(1)}\dots\alpha_{n+\tau(k-1)}; n=0,1,2,\dots\} where the ‘sup’ is taken over all subsequences 0=\tau(0)<\tau(1)<\dots<\tau(k-1) of integers of length k. We prove that \alpha is eventually periodic if and only if p_\alpha^*(k)\le 2k-1 for some k. Infinite words \alpha, with p_\alpha^*(k)=2k for any k, are called pattern Sturmian words and are studied.