next up previous
Next: Greibach Normal Form Transformation, Up: Abstracts Previous: A lower bound on

An $O(n \log n)$ Implementation of the Standard Method for Minimizing n-state Finite Automata

More than 20 years ago, Hopcroft (1971) has given an algorithm for minimizing an n-state finite automaton in $O(kn \log n)$ time where k is the size of the alphabet. This contrasts to the usual O(kn2) algorithms presented in text books. Since Hopcroft's algorithm changes the standard method, a nontrivial correctness proof for its method is needed. In lectures given at university, mostly the standard method and its straight forward O(kn2) implementation is presented. We show that a slight modification of the O(kn2) implementation combined with the use of a simple data structure composed of chained lists and four arrays of pointers (essentially the same as Hopcroft's data structure) leads to an $O(kn \log n)$ implementation of the standard method. Thus, it is possible to present in lectures, within a few additional amount of time, an $O(kn \log n)$ time algorithm for minimizing n-state finite automata.



Claus Rick
2000-05-10