On the Suffix Automaton with mismatches

Chiara Epifanio, Filippo Mignosi, Maxime Crochemore, Filippo Mignosi, Alessandra Gabriele

Risultato della ricerca: Otherpeer review

2 Citazioni (Scopus)

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.
Lingua originaleEnglish
Pagine144-156
Numero di pagine13
Stato di pubblicazionePublished - 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Entra nei temi di ricerca di 'On the Suffix Automaton with mismatches'. Insieme formano una fingerprint unica.

Cita questo