  Minimal deterministic finite automata (DFAs) can be reduced further at the
expense of a finite number of errors. Recently, such minimization algorithms
have been improved to run in time O(n log n), where n is the number of states
of the input DFA, by [Gawrychowski and Je\.z: Hyper-minimisation made
efficient. Proc. MFCS, LNCS 5734, 2009] and [Holzer and Maletti: An n log n
algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor.
Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as
possible, while only committing a finite number of errors. These algorithms are
further improved to return a DFA that commits the least number of errors at the
expense of an increased (quadratic) run-time. This solves an open problem of
[Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite
state automata. RAIRO Theor. Inf. Appl. 43, 2009]. In addition, an experimental
study on random automata is performed and the effects of the existing
algorithms and the new algorithm are reported.
