We use automata-theoretic approach to analyze properties of Fibonacci words. The directed acyclic subword graph (
dawg) is a useful deterministic automaton accepting all suffixes of the word. We show that
dawg's of Fibonacci words have particularly simple structure. Our main result is a unifying framework for a large collection of relatively simple properties of Fibonacci words. The simple structure of
dawgs of Fibonacci words gives in many cases simplified alternative proofs and new interpretation of several well-known properties of Fibonacci words. In particular, the structure of lengths of paths corresponds to a number-theoretic characterization of occurrences of any subword. Using the structural properties of
dawg's it can be easily shown that for a string
w we can check if
w is a subword of a Fibonacci word in time
O(|w|) and
O(1) space. Compact
dawg's of Fibonacci words show a very regular structure of their suffix trees and show how the suffix tree for the Fibonacci word grows (extending the leaves in a very simple way) into the suffix tree for the next Fibonacci word.
