Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 3471-3480 |
| Number of pages | 10 |
| Journal | Theoretical Computer Science |
| 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. / Gabriele, Alessandra; Epifanio, Chiara; Mignosi, Filippo; Crochemore, Maxime.
In: Theoretical Computer Science, 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 - Gabriele, Alessandra
AU - Epifanio, Chiara
AU - Mignosi, Filippo
AU - Crochemore, Maxime
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 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.
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 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.
KW - Combinatorics on words, Indexing, Suffix Automata, Languages with mismatches, Approximate string matching
UR - http://hdl.handle.net/10447/40047
M3 - Article
VL - 410
SP - 3471
EP - 3480
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -