A new algorithm for the construction of minimal acyclic DFAs

We present a semi-incremental algorithm for constructing minimal acyclic deterministic finite 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 final minimization step after the last word has been added (during construction).