Combinatorial Characterization of the Language Recognized by Factor and Suffix Oracles

Overview & Synopsis

Sequence Analysis requires to elaborate data structures which allow both an efficient storage and use. Among these, we can cite Tries, Suffix Automata, Suffix Trees. Cyril ALLAUZEN, Maxime CROCHEMORE and Mathieu RAFFINOT introduced a new data structure, linear on the size of the represented word both in time and space, having the smallest number of states, and allowing to accept at least all the substrings of the represented word. They called such a structure a Factor Oracle. On the basis of this structure, they developed another one having the same properties excepting the accordance of all the suffix of the represented word. They called it Suffix Oracle. The characterization of the language recognized by the Factor/Suffix Oracle of a word is an open problem for which we provide a solution.