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(kn²) 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(kn²) implementation is presented. We show that a slight modification of the O(kn²) 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.