论文标题
斐波那契和tribonacci单词的自动复杂性
Automatic complexity of Fibonacci and Tribonacci words
论文作者
论文摘要
对于复杂性函数$ c $，无限单词$ \ mathbf {x} $的下部和上部$ c $ - 复杂率是\ [ \ \ usewissline {c}（\ mathbf x）= \ liminf_ {n \ to \ infty} \ frac {c（\ mathbf {x} \ upharpoonRight n）} n，\ quad \ edline {c}（\ mathbf x）= \ limsup_ {n \ to \ infty} \ frac {c（\ mathbf {x} \ upharpoonRight n）} n \]。这里$ \ mathbf {x} \ upharpoonright n $是$ x $长度$ n $的前缀。我们考虑了$ c = \ mathrm {a_n} $，非确定自动复杂性。如果这些费率严格介于0到$ 1/2 $之间，我们将其称为中级。我们的主要结果是具有中间$ \ mathrm {a_n} $的单词存在，即。无限的斐波那契和Tribonacci词。
For a complexity function $C$, the lower and upper $C$-complexity rates of an infinite word $\mathbf{x}$ are \[ \underline{C}(\mathbf x)=\liminf_{n\to\infty} \frac{C(\mathbf{x}\upharpoonright n)}n,\quad \overline{C}(\mathbf x)=\limsup_{n\to\infty} \frac{C(\mathbf{x}\upharpoonright n)}n \] respectively. Here $\mathbf{x}\upharpoonright n$ is the prefix of $x$ of length $n$. We consider the case $C=\mathrm{A_N}$, the nondeterministic automatic complexity. If these rates are strictly between 0 and $1/2$, we call them intermediate. Our main result is that words having intermediate $\mathrm{A_N}$-rates exist, viz. the infinite Fibonacci and Tribonacci words.
