From Nerode's congruence to Suffix Automata with mismatches - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2009

From Nerode's congruence to Suffix Automata with mismatches

Résumé

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.
Fichier principal
Vignette du fichier
From_Nerode_s_congruence_to_Suffix_Automata_with_mismatches.pdf (201.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00741871 , version 1 (13-02-2013)

Identifiants

Citer

Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi. From Nerode's congruence to Suffix Automata with mismatches. Theoretical Computer Science, 2009, 410 (37), pp.3471-3480. ⟨10.1016/j.tcs.2009.03.011⟩. ⟨hal-00741871⟩
139 Consultations
380 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More