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

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)

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1971
Accession Number
AD0719398

Entities

People

  • John Hopcroft

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Alphabets
  • Automata
  • Machines

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Programming and Software Development.