6533b82dfe1ef96bd129093d
RESEARCH PRODUCT
On the suffix automaton with mismatches
Chiara EpifanioFilippo MignosiMaxime CrochemoreAlessandra Gabrielesubject
approximate string matchingFibonacci numberlanguages with mismatches[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Generalized suffix treeBüchi automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciences02 engineering and technology01 natural sciencesCombinatoricsPrefixCombinatorics on wordsDeterministic finite automaton010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringSuffix automaton020201 artificial intelligence & image processingsuffix automatacombinatorics on wordsComputer Science::Data Structures and Algorithmscombinatorics on words suffix automata languages with mismatches approximate string matchingWord (computer architecture)Computer Science::Formal Languages and Automata TheoryMathematicsdescription
International audience; In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k 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 well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2007-10-27 |