Incremental construction of minimal acyclic finite-state automata

Details Incremental construction of minimal acyclic finite-state automata Incremental construction of minimal acyclic finite-state automata

2000-07-06

arxiv.org/abs/cs/0007009v1

Computational Linguistics, Vol. 26, Number 1, March 2000

Computer Science

Computation and Language

14 pages, 7 figures

Scientific paper

In 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.

Affiliated with

Also associated with

No associations

Rating

Incremental construction of minimal acyclic finite-state automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Incremental construction of minimal acyclic finite-state automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental construction of minimal acyclic finite-state automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-17654