Incremental Construction of Compact Acyclic NFAs

Title: Incremental Construction of Compact Acyclic NFAs

Research Question: How can we efficiently construct non-deterministic finite-state automata (NFAs) that are compact and acyclic, especially useful for lexicon representation and fast string matching?

Methodology: The authors proposed an incremental algorithm for the construction of acyclic NFAs. This algorithm is an improvement over previous methods, as it creates NFAs that do not contain equivalent states. This property, while not ensuring minimality, results in NFAs that are considerably smaller than minimal DFAs for the same languages.

Results: The authors provided experimental results comparing the two structures using a lexicon of 230,000 words. They showed that the NFAs constructed by their algorithm were smaller than the minimal DFAs.

Implications: The algorithm presented in this paper offers a more efficient way to construct compact, acyclic NFAs, which are particularly useful in lexicon building, morphological processing, and speech processing. The incremental nature of the algorithm also allows for updates to the lexicon without rebuilding the entire structure, which is a significant advantage for real-time applications.

Link to Article: https://arxiv.org/abs/0201002v1 Authors: arXiv ID: 0201002v1