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

Maxime Crochemore 1 Laura Giambruno 2 Alessio Langiu 1
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Dipartimento di Matematica e Applicazioni [Palermo]
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.
Document type :
Journal articles
Complete list of metadatas
https://hal-upec-upem.archives-ouvertes.fr/hal-00836951
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 21, 2013 - 6:10:20 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM

Links full text

openaccess

Identifiers

Collections

ENPC | LIGM | PARISTECH | LIGM_ALGO | UNIV-MLV | UPEC-UPEM | LIGM_MOA

Citation

Maxime Crochemore, Laura Giambruno, Alessio Langiu. On-line construction of a small automaton for a finite set of words. International Journal of Foundations of Computer Science, World Scientific Publishing, 2012, 23 (2), pp.281-301. ⟨10.1142/S0129054112400138⟩. ⟨hal-00836951⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

232

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD