Maximal pattern complexity for discrete systems
Maximal pattern complexity for discrete systems
复制标题
DOI：
10.1017/s0143385702000585
复制
发表时间：
2002-08
影响因子：
0.9
通讯作者：
T. Kamae;L. Zamboni
中科院分区：
文献类型：
--
作者：
T. Kamae;L. Zamboni
对于一个在有限字母表上的无限字\(\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\}\)，其中上确界是对所有长度为\(k\)的整数序列\(0 = \tau(0) < \tau(1) < \cdots < \tau(k - 1)\)取的。作者证明了\(\alpha\)是非周期的当且仅当对于每个\(k = 1,2,\cdots\)，\(p_{\alpha}^*(k) \geq 2k\)。对于每个\(k\geq1\)，\(p_{\alpha}^*(k) = 2k\)的字\(\alpha\)被称为模式斯特姆字。在本文中，我们给出了一个成为模式斯特姆字的简单判别准则，并展示了一类新的循环模式斯特姆字，它们不是由旋转产生的。我们还研究了各种离散动力系统的最大模式复杂度，包括圆上的无理旋转以及由替换生成的自相似系统。我们表明，对于圆上的每个无理旋转，存在圆的一种双重划分，相对于此划分，所生成的系统以概率\(1\)具有完全最大模式复杂度。利用与替换动力系统相关的底层计数系统的算术性质，我们证明了劳齐替换\(1\mapsto12\)，\(2\mapsto13\)，\(3\mapsto1\)的不动点的最大模式复杂度具有指数增长。众所周知，由劳齐替换生成的系统在测度上同构于二维环面上的一个无理旋转。
For an infinite word \alpha=\alpha_0\alpha_1\alpha_2\dotsc over a finite alphabet, the authors introduced a new notion of complexity called maximal pattern complexity defined 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,\dotsc\} where the supremum is taken over all sequences of integers 0=\tau(0)<\tau(1)<\dotsc<\tau(k-1) of length k. The authors proved that \alpha is aperiodic if and only if p_\alpha^*(k)\ge 2k for every k=1,2,\dotsc. A word \alpha with p_\alpha^*(k)=2k for every k\geq 1 is called pattern Sturmian. In this paper, we give a simple criterion to be pattern Sturmian and exhibit a new class of recurrent pattern Sturmian words which do not arise from rotations. We also investigate the maximal pattern complexity of various discrete dynamical systems including irrational rotations on the circle, and self-similar systems generated by substitutions. We show that, for each irrational rotation on the circle, there exists a twofold partition of the circle, with respect to which the system generated has full maximal pattern complexity with probability one. Using the arithmetic properties of the underlying numeration system associated to a substitution dynamical system, we prove that the maximal pattern complexity of the fixed point of the Rauzy substitution 1\mapsto 12, 2\mapsto 13, 3\mapsto 1 has exponential growth. It is well known that the system generated by the Rauzy substitution is isomorphic in measure to an irrational rotation on the 2-torus.