Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

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 science
technical 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
72-151.pdf1.11 MBAdobe PDFView/Open
72-151.ps505.85 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us