From Nerode’s congruence to suffix automata with mismatches

Chiara Epifanio, Maxime Crochemore, Filippo Mignosi, Alessandra Gabriele

Risultato della ricerca: Articlepeer review

2 Citazioni (Scopus)


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 acharacterization of the Nerode''s right-invariant congruence that is associated withS_k. This result generalizes the classical characterization described in [5]. As secondresult we present an algorithm that makes use of S_k to accept in an efficient waythe 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 onsome 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 thesuffix automaton with mismatches.
Lingua originaleEnglish
pagine (da-a)3471-3480
Numero di pagine10
RivistaTheoretical Computer Science
Stato di pubblicazionePublished - 2009

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???


Entra nei temi di ricerca di 'From Nerode’s congruence to suffix automata with mismatches'. Insieme formano una fingerprint unica.

Cita questo