John Hopcroft gave a 1971 algorithm for minimizing deterministic finite automata with running time for states and alphabet . It refines partitions of states until states in the same block accept exactly the same continuation strings.[ref]
An n log n Algorithm for Minimizing States in a Finite Automaton by John Hopcroft. Introduction and Analysis of the running time
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 states, making representation size and equivalence checking algorithmic questions.
John Hopcroft, portrait published by Cornell University
. Articles by others on the same topic
John Hopcroft is a prominent American computer scientist known for his significant contributions to the fields of computer science, particularly in algorithms, automata theory, and graph theory. He is best known for his work in the development of efficient algorithms, and he co-authored the influential textbook "Introduction to Automata Theory, Languages, and Computation" with Rajeev Motwani and Jeffrey D. Ullman.