On the suffix automaton with mismatches

Maxime Crochemore 1 Chiara Epifanio 2 Alessandra Gabriele 2 Filippo Mignosi 3
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Dipartimento di Matematica e Applicazioni [Palermo]
3 DI - Dipartimento di Informatica [Italy]
Abstract : 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.
Keywords : combinatorics on words suffix automata languages with mismatches approximate string matching
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-00620159
Contributor : Maxime Crochemore <>
Submitted on : Monday, October 3, 2016 - 6:48:34 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Friday, February 3, 2017 - 3:14:43 PM

File

07-CEGM-ciaa.pdf
Files produced by the author(s)

Identifiers

Collections

LIGM | UPEC-UPEM | LIGM_MOA | CNRS | ENPC | PARISTECH

Citation

Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi. On the suffix automaton with mismatches. 12th International Conference on Implementation and Application of Automata (CIAA'07), 2007, Prague, Czech Republic. pp.144-156, ⟨10.1007/978-3-540-76336-9_15⟩. ⟨hal-00620159⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

270

Files downloads

171

Contact

CCSD