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 real dictionaries, on biological sequences and on the sets of suffixes (resp. factors) of a set of words that shows how our automaton is near to the minimal one. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. We moreover construct linear algorithms for the insertion and deletion of a word in a finite set, directly from the constructed automaton.

Crochemore, M., Giambruno, L., Langiu, A. (2012). ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, Volume 23, Issue 2 (2012)(Volume 23, Issue 2 (2012)), 281-301 [10.1142/S0129054112400138].

ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS

GIAMBRUNO, Laura;LANGIU, Alessio
2012-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 real dictionaries, on biological sequences and on the sets of suffixes (resp. factors) of a set of words that shows how our automaton is near to the minimal one. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. We moreover construct linear algorithms for the insertion and deletion of a word in a finite set, directly from the constructed automaton.
2012
Settore INF/01 - Informatica
Crochemore, M., Giambruno, L., Langiu, A. (2012). ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, Volume 23, Issue 2 (2012)(Volume 23, Issue 2 (2012)), 281-301 [10.1142/S0129054112400138].
File in questo prodotto:
File Dimensione Formato  
AbstractS0129054112400138.pdf

Solo gestori archvio

Descrizione: Abstract
Dimensione 84.86 kB
Formato Adobe PDF
84.86 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/62771
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact