Factor automata and special factors
Gabriele Fici · 2010
Abstract. The factor automaton of a finite word w is the minimal deter-ministic automaton recognizing the set of factors of w. It is a data structure allowing the search of a pattern in a text in time and space proportional to the length of the pattern. In this paper we link classical combinatorial parameters on words to the size and the structure of the factor automa-ton. As a main result, we give a characterization of the words having factor automaton with minimal number of states. 1