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