Computer Science – Information Theory
Scientific paper
2008-02-20
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.
Lehtinen Petri
Valmari Antti
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-647742