Use this link to cite:
http://hdl.handle.net/2183/146 Compilation methods of minimal acyclic finite-state automata for large dictionaries.
Loading...
Identifiers
Publication date
Authors
Advisors
Other responsabilities
Journal Title
Bibliographic citation
In Proceedings of the Sixth International Conference on Implementation and Application of Automata (CIAA-2001), Pretoria (Republic South Africa). Watson, B. W.; Wood, D. (eds.). Lecture Notes in Computer Science, vol. 2494, pp. 135-148.
Type of academic work
Academic degree
Abstract
[Abstract] We present a reflection on the evolution of the different methods for constructing minimal deterministic acyclic finite-state automata from a finite set of words. We outline the most important methods, including the traditional ones (which consist of the combination of two phases: insertion of words and minimization of the partial automaton) and the incremental algorithms (which add new words one by one and minimize the resulting automaton on-the-fly, being much faster and having significantly lower memory requirements). We analyze their main features in order to provide some improvements for incremental constructions, and a general architecture that is needed to implement large dictionaries in natural language processing (NLP) applications.