In this paper we focus on the construction of the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of Sk in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some wellknown words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
CROCHEMORE, M., EPIFANIO, C., GABRIELE, A., MIGNOSI, F. (2007). On the Suffix Automaton with mismatches. In Implementation and Application of Automata (pp.144-156). Springer Verlag.
On the Suffix Automaton with mismatches
EPIFANIO, Chiara;GABRIELE, Alessandra;MIGNOSI, Filippo
2007-01-01
Abstract
In this paper we focus on the construction of the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of Sk in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some wellknown words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
