Rank and symbolic complexity
Rank and symbolic complexity
复制标题
等级和符号复杂性
DOI：
--
复制
发表时间：
1996
影响因子：
0.9
通讯作者：
S. Ferenczi
中科院分区：
文献类型：
--
作者：
S. Ferenczi
摘要 我们研究了序列的复杂性函数（即长度为 n 的因子的数量 p(n)）与相关动力系统的等级（即近似该序列所需的 Rokhlin 塔的数量）之间的关系。我们证明，如果秩为 1，则为 lim ，但对于任何规定的函数 G，给出 lim 的例子，对于每个 a > 1，G (n) = 0(an) 。我们给出“楼梯”类型的示例的精确计算，这是具有二次复杂度的强混合系统。相反，对于最小序列，如果 p(n) < an + b 对于某些 a ≥ 1，则秩至多为 2[a]，且间隔字符串有界，并且系统由有限数量的替换生成。
Abstract We investigate the relation between the complexity function of a sequence, that is the number p(n) of its factors of length n, and the rank of the associated dynamical system, that is the number of Rokhlin towers required to approximate it. We prove that if the rank is one, then lim , but give examples with lim for any prescribed function G with G (n) = 0(an) for every a > 1. We give exact computations for examples of the ‘staircase’ type, which are strongly mixing systems with quadratic complexity. Conversely, for minimal sequences, if p(n) < an + b for some a ≥ 1, the rank is at most 2[a], with bounded strings of spacers, and the system is generated by a finite number of substitutions.