This chapter presents a new algorithm for incrementally building minimal acyclic deterministic finite automata. Such minimal automata are a compact representation of a finite set of words (e.g. in a spell checker). The incremental aspect of such algorithms (where the intermediate automaton is minimal) facilitates the construction of very large automata in limited computer memory where other
(nonincremental) algorithms would fail with intermediate data structures too large to fit in memory.
|Title of host publication||Grammars and automata for string processes : from mathematics and computer science to biology, and back : essays in honour of Gheorghe Paun|
|Editors||C. Martin-Vide, V. Mitrana|
|Publisher||Taylor and Francis Ltd.|
|Publication status||Published - 2003|
|Name||Topics in Computer Mathematics|