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
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.