On the Suffix Automaton with mismatches

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

Risultato della ricerca: Other

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)

Cita questo

Mignosi, F., Epifanio, C., Crochemore, M., Mignosi, F., & Gabriele, A. (2007). On the Suffix Automaton with mismatches. 144-156.

On the Suffix Automaton with mismatches. / Mignosi, Filippo; Epifanio, Chiara; Crochemore, Maxime; Mignosi, Filippo; Gabriele, Alessandra.

2007. 144-156.

Risultato della ricerca: Other

Mignosi, F, Epifanio, C, Crochemore, M, Mignosi, F & Gabriele, A 2007, 'On the Suffix Automaton with mismatches', pagg. 144-156.
Mignosi F, Epifanio C, Crochemore M, Mignosi F, Gabriele A. On the Suffix Automaton with mismatches. 2007.
Mignosi, Filippo ; Epifanio, Chiara ; Crochemore, Maxime ; Mignosi, Filippo ; Gabriele, Alessandra. / On the Suffix Automaton with mismatches. 13 pag.
@conference{a34e44dcf19f40888cbae9c7428e312b,
title = "On the Suffix Automaton with mismatches",
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.",
author = "Filippo Mignosi and Chiara Epifanio and Maxime Crochemore and Filippo Mignosi and Alessandra Gabriele",
year = "2007",
language = "English",
pages = "144--156",

}

TY - CONF

T1 - On the Suffix Automaton with mismatches

AU - Mignosi, Filippo

AU - Epifanio, Chiara

AU - Crochemore, Maxime

AU - Mignosi, Filippo

AU - Gabriele, Alessandra

PY - 2007

Y1 - 2007

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

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

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

M3 - Other

SP - 144

EP - 156

ER -