Skip to Main content Skip to Navigation
Journal articles

From Nerode's congruence to Suffix Automata with mismatches

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00741871
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 11:28:54 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:02 AM

File

From_Nerode_s_congruence_to_Su...
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi. From Nerode's congruence to Suffix Automata with mismatches. Theoretical Computer Science, Elsevier, 2009, 410 (37), pp.3471-3480. ⟨10.1016/j.tcs.2009.03.011⟩. ⟨hal-00741871⟩

Share

Metrics

Record views

337

Files downloads

387