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