Decision algorithms for Fibonacci-automatic Words, I: Basic results

Abstract

We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) “Fibonacci-automatic”. This class includes, for example, the famous Fibonacci word f = f 0 f 1 f 2 ··· = 01001010··· , the fixed point of the morphism 0 → 01 and 1 → 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth.