Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Describing an Algorithm by Hopcroft

Describing an Algorithm by Hopcroft

File(s)
72-151.pdf (1.08 MB)
72-151.ps (505.85 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6002
Collections
Computer Science Technical Reports
Author
Gries, David
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.

Date Issued
1972-12
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-151
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance