Incremental Construction of Compact Acyclic NFAs

Simple item page
dc.creatorSgarbas, Kyriakos N.
dc.creatorFakotakis, Nikos D.
dc.creatorKokkinakis, George K.
dc.date2002-01-04
dc.date.accessioned2026-07-07T03:18:03Z
dc.date.available2026-07-07T03:18:03Z
dc.descriptionThis 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.
dc.description8(+2) pages, 4 figures, 1 table, 22 references. For related work, see also http://slt.wcl.ee.upatras.gr
dc.identifierhttps://arxiv.org/abs/cs/0201002
dc.identifierhttp://arxiv.org/abs/cs/0201002
dc.identifierProc. ACL-2001, 39th Annual Meeting of the Association for Computational Linguistics, pp.474-481, Toulouse, France, 6-11 July 2001
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30956
dc.subjectData Structures and Algorithms
dc.subjectComputation and Language
dc.subjectE.1; F.2.2; H.3.1; I.2.7
dc.titleIncremental Construction of Compact Acyclic NFAs
dc.typetext

Files

Collections

arXiv