Skip to content
Publications

Article

Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries

Jorge Graña, Fco. Mario Barcala, Miguel Á. Alonso

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.

semigroups and automata theoryNatural Language Processing TechniquesAlgorithms and Data Compressionacyclic automataautomata constructionincremental algorithms

More by Miguel Alonso