 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [27 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00741871
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 11:28:54 AM
Last modification on : Saturday, January 15, 2022 - 3:56:42 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:02 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 11:28:54 AM
Last modification on : Saturday, January 15, 2022 - 3:56:42 AM
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)