Incremental Construction of Compact Acyclic NFAs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
8(+2) pages, 4 figures, 1 table, 22 references. For related work, see also http://slt.wcl.ee.upatras.gr

Keywords

Data Structures and Algorithms, Computation and Language, E.1; F.2.2; H.3.1; I.2.7

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30956

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0201002
 http://arxiv.org/abs/cs/0201002
 Proc. ACL-2001, 39th Annual Meeting of the Association for Computational Linguistics, pp.474-481, Toulouse, France, 6-11 July 2001

Collections

arXiv