6533b7cffe1ef96bd1258f1a
RESEARCH PRODUCT
ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS
Alessio LangiuAlessio LangiuLaura GiambrunoMaxime Crochemoresubject
minimal automata[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Timed automatondeterministic automataBüchi automaton0102 computer and information sciences02 engineering and technology01 natural sciencesDeterministic automaton0202 electrical engineering electronic engineering information engineeringComputer Science (miscellaneous)Two-way deterministic finite automatonNondeterministic finite automatonMathematicsonline construction.Discrete mathematicsSettore INF/01 - InformaticaPowerset constructionPushdown automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)010201 computation theory & mathematicsProbabilistic automaton020201 artificial intelligence & image processingFinite set of wordAlgorithmComputer Science::Formal Languages and Automata Theorydescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-02-01 |