Accession Number : AD0719398

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

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hopcroft,John

Report Date : JAN 1971

Pagination or Media Count : 15

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)

Descriptors :   (*COMPUTER PROGRAMMING, ALGORITHMS), (*DIGITAL COMPUTERS, SWITCHING CIRCUITS), LOGIC CIRCUITS, COMPUTER LOGIC, COMPUTER PROGRAMS, OPTIMIZATION, AUTOMATA

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE