Complexity of Linear Subsequences of Fibonacci-Automatic Sequences

Delaram Moradi, Narad Rampersad, Jeffrey Shallit

We construct automata with input(s) in Fibonacci representation (also known as Zeckendorf representation) recognizing some basic arithmetic relations and study their number of stat…