www.elsevier.com/locate/scico A new algorithm for the construction of minimal acyclic DFAs

We present a semi-incremental algorithm for constructing minimal acyclic deterministic /nite automata. Such automata are useful for storing sets of words for spell-checking, among other applications. The algorithm is semi-incremental because it maintains the automaton in nearly minimal condition and requires a /nal minimization step after the last word has been added (during construction). The algorithm derivation proceeds formally (with correctness arguments) from two separate algorithms, one for minimization and one for adding words to acyclic automata. The algorithms are derived in such a way as to be combinable, yielding a semi-incremental one. In practice, the algorithm is both easy to implement and displays good running time performance