= John Hopcroft
{c}
= John E. Hopcroft
{c}
{synonym}
<John Hopcroft> gave a 1971 algorithm for minimizing deterministic finite automata with running time $O(|\Sigma|n\log n)$ for $n$ <state (computer science)>[states] and alphabet $\Sigma$. It refines partitions of <state (computer science)>[states] until <state (computer science)>[states] in the same block accept exactly the same continuation <string>[strings].<An n log n Algorithm for Minimizing States in a Finite Automaton by John Hopcroft>[Introduction and Analysis of the running time]{ref}
The key accounting idea is to organize refinement around smaller splitters. A transition can then be charged to only logarithmically many successively smaller blocks, instead of rescanning every state in every refinement round. <DFA minimization> preserves the recognized language while merging observationally equivalent <state (computer science)>[states], making representation size and equivalence checking algorithmic questions.
\Image[https://www.cs.cornell.edu/sites/default/files/2025-06/0781_07_a_014_select.jpg]
{title=<John Hopcroft>, portrait published by Cornell University}
Back to article page
