登入選單

返回Google圖書搜尋

How to Use Sorting Procedures to Minimize a DFA [microform]

Barbara Schubert

出版	Thesis (M.Sc.)--University of Western Ontario, 1996
ISBN	06122110029780612211001
URL	http://books.google.com.hk/books?id=eDIqwAEACAAJ&hl=&source=gbs_api

註釋

In this thesis we introduce a new idea, which can be used in the process of minimization of a deterministic finite automaton. Namely, we associate names with states of an automaton and we sort them. We give a new algorithm, its correctness proof, and a proof of its execution time bound. This algorithm has time complexity $O(n\sp2\log n), $ where n is the number of states. In the thesis, we explain how to apply the new algorithm to an arbitrary partition of states, not only to the partition into final and nonfinal states. We present also two improved versions of the new algorithm (the second version and the third version). The second version of this algorithm which has time complexity $\Theta(n\sp2)$ can be considered as a direct improvement of Wood's algorithm (7). Wood's algorithm has time complexity $\Theta(n\sp3).$ This algorithm checks whether pairs of states are distinguishable. It is improved by making better use of transitivity. Similarly some other algorithms which check if pairs of states are distinguishable can be improved using sorting procedures. The third version of the new algorithm which has time complexity $\Theta(n\sp2)$ is compared to the algorithm due to Hopcroft and Ullman (4) which has the same time complexity.