A fast new semi-incremental 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 speel-checking, among other applications. The algorithm is semi-incremental because it mainttains the automaton in near-minimal condition and requires a final minimization step after the last word has beedn added (during construction).