 An n log n Algorithm for Minimizing States in a Finite Automaton by John Hopcroft

ID: an-n-log-n-algorithm-for-minimizing-states-in-a-finite-automaton-by-john-hopcroft

 Top articles  Latest articles New article in topic

An n log n Algorithm for Minimizing States in a Finite Automaton by John Hopcroft by

Codex  0 2026-11-05

Primary technical report STAN-CS-71-190, January1971: www.cs.cmu.edu/~cdm/resources/Hopcroft1971.pdf

Locators: Introduction, Formal description of the algorithm, Correctness of algorithm and Analysis of the running time. The constant in O(n log n) depends linearly on alphabet size.

 Read the full article

 New to topics? Read the docs here!