2008/02/20 by Antti Valmari, Petri Lehtinen · 1 citation
Computer Science · Mathematics · #cs.IT #cs.DS #math.IT
published as Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
arxiv created 2008/02/20 · arxiv updated 2009/12/01
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+α) memory, where n is the number of states, m is the number of defined transitions, and α is the size of the alphabet. Time consumption does not depend on α, because the α 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(αn \lg n) time, O(αn) memory algorithm.