CLR cover
Previous problem

Problem 103: A Compact Factor Automaton

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\fib{\mathit{fib}} \def\gib{\mathit{g}} \)

A Factor automaton is a minimal (deterministic) automaton accepting all the factors of a word. It is also called a directed acyclic word graph (DAWG). All its states are terminal and its edges are labelled by single letters. For certain well-structured words the automaton can be highly compressed by removing nodes having exactly one parent and one child and labelling edges by factors of the word accordingly. The resulting DAWG is called a compact DAWG (CDAWG) or compact Suffix automaton (CSA) if nodes corresponding to suffixes are marked as terminal.

The problem considers words whose CDAWGs are extremely small, namely Fibonacci words $\fib_n$ and their shortened version $\gib_n$. The word $\gib_n$ is $\fib_n$ with the last two letters deleted, that is, $\gib_n = \fib_n\{\sa{a},\sa{b}\}^{-2}$.

Describe the structure of CDAWGs of Fibonacci words $\fib_n$ and of their trimmed versions $\gib_n$. Using this structure compute the number of distinct factors occurring in the words.

References

  • P. Baturo, M. Piatkowski, and W. Rytter. Usefulness of directed acyclic subword graphs in problems related to standard sturmian words. Int. J. Found. Comput. Sci., 20(6):1005-1023, 2009.
  • W. Rytter. The structure of subword graphs and suffix trees of Fibonacci words. Theor. Comput. Sci., 363(2):211-223, 2006.