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

Laura Giambruno, Maxime Crochemore, Alessio Langiu, Alessio Langiu

Risultato della ricerca: Articlepeer review

1 Citazioni (Scopus)

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.
Lingua originaleEnglish
pagine (da-a)281-301
Numero di pagine21
RivistaInternational Journal of Foundations of Computer Science
VolumeVolume 23, Issue 2 (2012)
Stato di pubblicazionePublished - 2012

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Fingerprint Entra nei temi di ricerca di 'ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS'. Insieme formano una fingerprint unica.

Cita questo