In this paper we focus on the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. As first results we give a characterization of the Nerode''s right-invariant congruence that is associated with S_k. This result generalizes the classical characterization described in [5]. As second result we present an algorithm that makes use of S_k to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.

Crochemore, M., Epifanio, C., Gabriele, A., Mignosi, F. (2009). From Nerode’s congruence to suffix automata with mismatches. THEORETICAL COMPUTER SCIENCE, 410(37), 3471-3480 [10.1016/j.tcs.2009.03.011].

From Nerode’s congruence to suffix automata with mismatches

EPIFANIO, Chiara;GABRIELE, Alessandra;
2009-01-01

Abstract

In this paper we focus on the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. As first results we give a characterization of the Nerode''s right-invariant congruence that is associated with S_k. This result generalizes the classical characterization described in [5]. As second result we present an algorithm that makes use of S_k to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.
2009
Settore INF/01 - Informatica
Crochemore, M., Epifanio, C., Gabriele, A., Mignosi, F. (2009). From Nerode’s congruence to suffix automata with mismatches. THEORETICAL COMPUTER SCIENCE, 410(37), 3471-3480 [10.1016/j.tcs.2009.03.011].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/40047
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact