A fast and simple algorithm for constructing minimal acyclic deterministic finite automata

B.W. Watson

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

6 Citaten (Scopus)
75 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)363-367
TijdschriftJournal of Universal Computer Science
Volume8
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 2002

Vingerafdruk

Duik in de onderzoeksthema's van 'A fast and simple algorithm for constructing minimal acyclic deterministic finite automata'. Samen vormen ze een unieke vingerafdruk.

Citeer dit