
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