From Nerode’s congruence to suffix automata with mismatches

Chiara Epifanio, Maxime Crochemore, Filippo Mignosi, Alessandra Gabriele

Risultato della ricerca: Article

2 Citazioni (Scopus)

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 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
RivistaDefault journal
Volume410
Stato di pubblicazionePublished - 2009

Fingerprint

Suffix
Congruence
Automata
Deterministic Finite Automata
Finite automata
Prefix
Open Problems
Generalise
Invariant
Experimental Results
Text
Repetition
Language

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Epifanio, C., Crochemore, M., Mignosi, F., & Gabriele, A. (2009). From Nerode’s congruence to suffix automata with mismatches. Default journal, 410, 3471-3480.

From Nerode’s congruence to suffix automata with mismatches. / Epifanio, Chiara; Crochemore, Maxime; Mignosi, Filippo; Gabriele, Alessandra.

In: Default journal, Vol. 410, 2009, pag. 3471-3480.

Risultato della ricerca: Article

Epifanio, C, Crochemore, M, Mignosi, F & Gabriele, A 2009, 'From Nerode’s congruence to suffix automata with mismatches', Default journal, vol. 410, pagg. 3471-3480.
Epifanio C, Crochemore M, Mignosi F, Gabriele A. From Nerode’s congruence to suffix automata with mismatches. Default journal. 2009;410:3471-3480.
Epifanio, Chiara ; Crochemore, Maxime ; Mignosi, Filippo ; Gabriele, Alessandra. / From Nerode’s congruence to suffix automata with mismatches. In: Default journal. 2009 ; Vol. 410. pagg. 3471-3480.
@article{f03fffb0754f4b0a85a2b4e924759c16,
title = "From Nerode’s congruence to suffix automata with mismatches",
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 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.",
keywords = "Approximate string matching, Combinatorics on words, Indexing, Languages with mismatches, Suffix Automata",
author = "Chiara Epifanio and Maxime Crochemore and Filippo Mignosi and Alessandra Gabriele",
year = "2009",
language = "English",
volume = "410",
pages = "3471--3480",
journal = "Default journal",

}

TY - JOUR

T1 - From Nerode’s congruence to suffix automata with mismatches

AU - Epifanio, Chiara

AU - Crochemore, Maxime

AU - Mignosi, Filippo

AU - Gabriele, Alessandra

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Approximate string matching

KW - Combinatorics on words

KW - Indexing

KW - Languages with mismatches

KW - Suffix Automata

UR - http://hdl.handle.net/10447/40047

M3 - Article

VL - 410

SP - 3471

EP - 3480

JO - Default journal

JF - Default journal

ER -