Incremental construction of minimal acyclic finite-state automata

Simple item page
dc.creatorDaciuk, Jan
dc.creatorMihov, Stoyan
dc.creatorWatson, Bruce
dc.creatorWatson, Richard
dc.date2000-07-06
dc.date.accessioned2026-07-07T03:16:20Z
dc.date.available2026-07-07T03:16:20Z
dc.descriptionIn this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings. Traditional methods consist of two phases: the first to construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering of the input strings.
dc.description14 pages, 7 figures
dc.identifierhttps://arxiv.org/abs/cs/0007009
dc.identifierhttp://arxiv.org/abs/cs/0007009
dc.identifierComputational Linguistics, Vol. 26, Number 1, March 2000
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30317
dc.subjectComputation and Language
dc.subjectI.2.7
dc.titleIncremental construction of minimal acyclic finite-state automata
dc.typetext

Files

Collections

arXiv