Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6002
 Title: Describing an Algorithm by Hopcroft Authors: Gries, David Keywords: computer sciencetechnical report Issue Date: Dec-1972 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-151 Abstract: We give an algorithm, its correctness proof, and its proof of execution time bound, for finding the sets of equivalent states in a deterministic finite state automaton. The time bound is $K\cdotm\cdot\n\cdot\\log n$ where $K$ is a constant, $m$ the number of input symbols, and $n$ the number of states. Hopcroft [3] has already published such an algorithm. The main reason for this paper is to illustrate the use of communicating an algorithm to others using a structured, top-down approach. We have also been able to improve on Hopcroft's algorithm by reducing the size of the algorithm and correspondingly complicating the proof of the running time bound. URI: http://hdl.handle.net/1813/6002 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat