Accession Number:

AD0719398

Title:

An N Log N Algorithm for Minimizing States in a Finite Automaton,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1971-01-01

Pagination or Media Count:

15.0

Abstract:

An algorithm is given for minimizing the number of states in a finite automaton or for determining if two automata are equivalent. The asymptotic running time of the algorithm is bounded by k n log n where k is some constant and n is the number of states. The constant k depends linearly on the size of the input alphabet. Author

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE