Incremental construction of minimal acyclic finite state automata and transducers
Jan Daciuk, Bruce W. Watson, Richard E. Watson · 1998
In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite state automata and transducers. Traditional methods consist of two steps. The first one is to construct a trie, the second one --- to perform minimization. Our approach is to construct an automaton in a single step by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical sorting of the input strings.