Not as Fast, But Fewer Errors
Andreas Maletti · 2011
Hyper-minimization aims to compute a minimal determinis- tic 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 timeO(nlog n) ,w heren is the number of states of the given dfa, have been reported recently in (Gawrychowski and Jez :H yper- minimisation made efficient. Proc. Mfcs, Lncs 5734, 2009) and (Holzer and Maletti :A nnlog n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010). These algo- rithms are improved to return a hyper-minimal dfa that commits the least number of errors. This closes another open problem of (Badr, Gef- fert ,a ndShipman: 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 ).