We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS.
- Authors
CROCHEMORE, MAXIME; GIAMBRUNO, LAURA; LANGIU, ALESSIO; Holub, J.
- 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.
- Subjects
ROBOTS; SET theory; ALGORITHMS; MACHINE theory; LINEAR time invariant systems; LINEAR systems
- Publication
International Journal of Foundations of Computer Science, 2012, Vol 23, Issue 2, p281
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054112400138