Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 2

available in:   PDF (84 kB) PS (100 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-02-0363


A Fast and Simple Algorithm for Constructing Minimal Acyclic Deterministic Finite Automata

Bruce W. Watson (Software Construction Research Group, Department of Computer Science, Technological University of Eindhoven, the Netherlands; Department of Computer Science, University of Pretoria, South Africa; FST Labs & Ribbit Software Systems Inc.)

Abstract: In this paper, we present a fast and simple algorithm for constructing a minimal acyclic deterministic finite automaton from a denite set of words. Such automata are useful in a wide variety of applications, including computer virus detection, computational linguistics and computational genetics. There are several known algorithms that solve the same problem, though most of the alternative algorithms are considerably more difficult to present, understand and implement than the one given here. Preliminary benchmarking indicates that the algorithm presented here is competitive with the other known algorithms.

1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut J├╝rgensen.

Keywords: automata construction algorithms, minimal acyclic deterministic finite automata

Categories: F.1.1