Abstract
Sequence Analysis requires to elaborate data structures, which allow both an efficient storage and use. A new one was introduced in 1999 by Cyril Allauzen, Maxime Crochemore and Mathieu Raffinot. This structure is linear on the size of the represented word both in time and space. It has the smallest number of states and it accepts at least all substrings of the represented word. This structure is called Factor Oracle. Authors developed another structure on the basis of Factor Oracle, which has the same properties except it accepts at least all suffixes instead of all factors of the represented word. This structure is then called Suffix Oracle. The characterization of the language recognized by the Factor/Suffix Oracle of a given word is an open problem, for which we provide a solution. Using this result, we show that these structures may accept an exponential number of words, which are not factors/suffixes of the given word.