Report Number: CS-TR-71-190
Institution: Stanford University, Department of Computer Science
Title: An n log n algorithm for minimizing states in a finite automaton
Author: Hopcroft, John E.
Date: January 1971
Abstract: An algorithm is given for minimizing the number of states in a finite automaton or for determining if two finite automata are equivalent. The asymptotic running time of the algorithm is bounded by k n log n where k is some constant and n is the number of states. The constant k depends linearly on the size of the input alphabet.
http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf