Skip to main content


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

Please use this identifier to cite or link to this item:
Title: Describing an Algorithm by Hopcroft
Authors: Gries, David
Keywords: computer science
technical report
Issue Date: Dec-1972
Publisher: Cornell University
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.
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