Automatic complexity of Fibonacci and Tribonacci words

2020/10/14 by Kjos-Hanssen, Bjørn · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2010.07275

Abstract

For a complexity function C, the lower and upper C-complexity rates of an infinite word x are \underlineC(\mathbf x)=\liminf_n→∞ \fracC(x\upharpoonright n)n, C(\mathbf x)=\limsup_n→∞ \fracC(x\upharpoonright n)n respectively. Here x\upharpoonright n is the prefix of x of length n. We consider the case C=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 A_N-rates exist, viz. the infinite Fibonacci and Tribonacci words.

Cited by

• Languages of Words of Low Automatic Complexity Are Hard to Compute

Related

• Initial non-repetitive complexity of infinite words
• Improvement Ergodic Theory For The Infinite Word \mathfrakF=\mathfrakF_b:=( _b f_n)_{n \geqslant 0} on Fibonacci Density
• N-factor complexity of the infinite Fibonacci sequence and digital sequences
• Additive word complexity and Walnut
• Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance