The Prague Stringology Conference 2004
Alban Mancheron and Christophe Moan
Combinatorial Characterization of the Language Recognized by Factor and Suffix Oracles
| Abstract: |
|
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. |
| Download paper: |  |
 |
| PostScript |