Name
Abstract | ||
|---|---|---|
In this paper we focus on the construction of the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of Sk in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some wellknown words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-76336-9_15 | CIAA |
Keywords | Field | DocType |
wellknown word,minimal deterministic finite automaton,repetition index,suffix automaton,thue-morse word,word w,k error,approximate string matching,combinatorics on words | Combinatorics,Suffix automaton,Deterministic finite automaton,Prefix,Approximate string matching,Generalized suffix tree,Mathematics,Combinatorics on words,Büchi automaton,Fibonacci number | Conference |
Volume | ISSN | ISBN |
4783 | 0302-9743 | 3-540-76335-X |
Citations | PageRank | References |
2 | 0.38 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Chiara Epifanio | 2 | 36 | 4.33 |
| A. Gabriele | 3 | 24 | 3.37 |
| Filippo Mignosi | 4 | 569 | 99.71 |