Automatic complexity of Fibonacci and tribonacci words (Q2217496)

The nondeterministic automatic complexity \(A_N(x)\) of a word \(x\) is defined as the smallest number of states in a non-deterministic automaton that accepts the word \(x\) and does not accept any other words of the same length. The \(A_N\)-complexity rate \(A_N(x)\) of an infinite word \(x=x_1x_2\ldots\) is defined as the limit of the ratio \(A_N(x_1\ldots x_n)/n\). When this limit is defined, it is always between 0 and 1/2. Random infinite sequences have \(A_N(x)=1/2\), periodic sequences have \(A_N(x)=0\); however, until now, no infinite words were known with intermediate values of \(A_N\)-complexity rate. The paper provides the first examples of infinite words for which \(0<A_N(x)<1/2\): Fibonacci and tribonacci words. The Fibonacci word is defined as the limit of a sequence \(F_0=\varepsilon\), \(F_1=1\), \(F_2=0\), and \(F_n=F_{n-1}F_{n-2}\) for \(n\ge 3\). The name comes from the fact that the length of \(F_n\) is the \(n\)-th Fibonacci number. A tribonacci word is the limit of a similarly defined sequence \(T_0=T_1=\varepsilon\), \(T_2=2\), \(T_3=0\), \(T_4=01\), and \(T_n=T_{n-1}T_{n-2}T_{n-3}\) for \(n\ge 5\).