Describing an nlogn algorithm for minimizing states in deterministic nite automaton
Yingjie Xu · 2009
There are several well known algorithms to minimize deterministic nite automata. In this paper, an algorithm is given for minimizing the number of states in a nite automaton or for determining if two nite automata are equivalent. The asymptotic running time of the algorithm is bounded by knlogn where k is some constant depends linearly on the size of the input alphabet and n is the number of states.