Efficient Minimization of DFAs with Partial Transition Functions

Details Efficient Minimization of DFAs with Partial Transition Functions Efficient Minimization of DFAs with Partial Transition Functions

2008-02-20

arxiv.org/abs/0802.2826v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Information Theory

Scientific paper

Let PT-DFA mean a deterministic finite automaton whose transition relation is a partial function. We present an algorithm for minimizing a PT-DFA in $O(m \lg n)$ time and $O(m+n+\alpha)$ memory, where $n$ is the number of states, $m$ is the number of defined transitions, and $\alpha$ is the size of the alphabet. Time consumption does not depend on $\alpha$, because the $\alpha$ term arises from an array that is accessed at random and never initialized. It is not needed, if transitions are in a suitable order in the input. The algorithm uses two instances of an array-based data structure for maintaining a refinable partition. Its operations are all amortized constant time. One instance represents the classical blocks and the other a partition of transitions. Our measurements demonstrate the speed advantage of our algorithm on PT-DFAs over an $O(\alpha n \lg n)$ time, $O(\alpha n)$ memory algorithm.

Affiliated with

Also associated with

No associations

Rating

Efficient Minimization of DFAs with Partial Transition Functions 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 Efficient Minimization of DFAs with Partial Transition Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Minimization of DFAs with Partial Transition Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647742