ABSTRACT
Among finite-state automata, acyclic automata play an important role inmany applications. For example, they are often used as dictionaries in natural language processing and computational linguistics (including speech processing), as well as compiler construction. A language of an acyclic automaton is a finite set of finite-length strings. To speed-up processing, deterministic automata are used as they do not require backtracking. To save space, the automata are minimal.
