Abstract
Original language | English |
---|---|
Pages (from-to) | 3471-3480 |
Number of pages | 10 |
Journal | Default journal |
Volume | 410 |
Publication status | Published - 2009 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Cite this
From Nerode’s congruence to suffix automata with mismatches. / Epifanio, Chiara; Crochemore, Maxime; Mignosi, Filippo; Gabriele, Alessandra.
In: Default journal, Vol. 410, 2009, p. 3471-3480.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - From Nerode’s congruence to suffix automata with mismatches
AU - Epifanio, Chiara
AU - Crochemore, Maxime
AU - Mignosi, Filippo
AU - Gabriele, Alessandra
PY - 2009
Y1 - 2009
N2 - 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 acharacterization of the Nerode''s right-invariant congruence that is associated withS_k. This result generalizes the classical characterization described in [5]. As secondresult we present an algorithm that makes use of S_k to accept in an efficient waythe 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 onsome 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 thesuffix automaton with mismatches.
AB - 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 acharacterization of the Nerode''s right-invariant congruence that is associated withS_k. This result generalizes the classical characterization described in [5]. As secondresult we present an algorithm that makes use of S_k to accept in an efficient waythe 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 onsome 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 thesuffix automaton with mismatches.
KW - Approximate string matching
KW - Combinatorics on words
KW - Indexing
KW - Languages with mismatches
KW - Suffix Automata
UR - http://hdl.handle.net/10447/40047
M3 - Article
VL - 410
SP - 3471
EP - 3480
JO - Default journal
JF - Default journal
ER -