Incremental Construction of Compact Acyclic NFAs

2002/01/04 by Kyriakos N. Sgarbas, Nikos D. Fakotakis, George K. Kokkinakis
Computer Science · #cs.DS #cs.CL

paper · pdf

published as Proc. ACL-2001, 39th Annual Meeting of the Association for Computational Linguistics, pp.474-481, Toulouse, France, 6-11 July 2001 · 8(+2) pages, 4 figures, 1 table, 22 references. For related work, see also http://slt.wcl.ee.upatras.gr

arxiv created 2002/01/04 · arxiv updated 2009/11/30

Abstract

This paper presents and analyzes an incremental algorithm for the construction of Acyclic Non-deterministic Finite-state Automata (NFA). Automata of this type are quite useful in computational linguistics, especially for storing lexicons. The proposed algorithm produces compact NFAs, i.e. NFAs that do not contain equivalent states. Unlike Deterministic Finite-state Automata (DFA), this property is not sufficient to ensure minimality, but still the resulting NFAs are considerably smaller than the minimal DFAs for the same languages.

Related

• Incremental construction of minimal acyclic finite-state automata
• Exact generation of acyclic deterministic finite automata
• Minimal Nondeterministic Finite Automata and Atoms of Regular Languages
• On NFAs Where All States are Final, Initial, or Both
• Incremental Construction of Minimal Acyclic Sequential Transducers from Unsorted Data