Paper: Transforming Lattices into Non-deterministic Automata with Optional Null Arcs

ACL ID P98-2197
Title Transforming Lattices into Non-deterministic Automata with Optional Null Arcs
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998
Authors

The problem of transforming a lattice into a non-deterministic finite state automaton is non-trivial. We present a transformation al- gorithm which tracks, for each node of an automaton under construction, the larcs which it reflects and the lattice nodes at their origins and extremities. An extension of the algorithm permits the inclusion of null, or epsilon, arcs in the output automaton. The algorithm has been successfully applied to lattices derived from dictionaries, i.e. very large corpora of strings.