In this paper we describe a ``light'' algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on the suffixes of a text, showing how this automaton is small. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton.

Crochemore, M., Giambruno, L. (2009). On-line construction of a small automaton for a finite set of words. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? Prague Stringology Conference 2009, Praga, Repubblica ceca.

On-line construction of a small automaton for a finite set of words

GIAMBRUNO, Laura
2009-01-01

Abstract

In this paper we describe a ``light'' algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on the suffixes of a text, showing how this automaton is small. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton.
2009
Prague Stringology Conference 2009
Praga, Repubblica ceca
2009
14
Crochemore, M., Giambruno, L. (2009). On-line construction of a small automaton for a finite set of words. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? Prague Stringology Conference 2009, Praga, Repubblica ceca.
Proceedings (atti dei congressi)
Crochemore, M; Giambruno, L
File in questo prodotto:
File Dimensione Formato  
Croch_Giambr.pdf

Solo gestori archvio

Descrizione: articolo principale
Dimensione 197.82 kB
Formato Adobe PDF
197.82 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/40309
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact