Combinatorial Characterization of the Language Recognized by Factor and Suffix OraclesReportar como inadecuado




Combinatorial Characterization of the Language Recognized by Factor and Suffix Oracles - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 MAB - Méthodes et Algorithmes pour la Bioinformatique LIRMM - Laboratoire d-Informatique de Robotique et de Microélectronique de Montpellier 2 LINA - Laboratoire d-Informatique de Nantes Atlantique

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.

Keywords : Factor Oracle Suffix Oracle automata language characterization





Autor: Alban Mancheron - Christophe Moan -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados