Skip to main content
Passa alla visualizzazione normale.

CHIARA EPIFANIO

From Nerode’s congruence to suffix automata with mismatches

  • Authors: Crochemore, M; Epifanio, C; Gabriele, A; Mignosi, F
  • Publication year: 2009
  • Type: Articolo in rivista (Articolo in rivista)
  • Key words: Combinatorics on words, Indexing, Suffix Automata, Languages with mismatches, Approximate string matching
  • OA Link: http://hdl.handle.net/10447/40047

Abstract

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 a characterization of the Nerode''s right-invariant congruence that is associated with S_k. This result generalizes the classical characterization described in [5]. As second result we present an algorithm that makes use of S_k to accept in an efficient way the 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 on some 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 the suffix automaton with mismatches.