Better hyper-minimization: not as fast, but fewer errors
Andreas Maletti · arXiv (Cornell University) · 2010
Abstract. Hyper-minimization aims to compute a minimal deterministic finite automaton (dfa) that recognizes the same language as a given dfa up to a finite number of errors. Algorithms for hyper-minimization that run in time O(n log n), where n is the number of states of the given dfa, have been reported recently in [Gawrychowski and Jeż: Hyperminimisation 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]. These algorithms are improved to return a hyper-minimal dfa that commits the least number of errors. This closes another open problem of [Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite state automata. Rairo Theor. Inf. Appl. 43, 2009]. Unfortunately, the time complexity for the obtained algorithm increases to O(n 2). 1