Notes on Hyper-minimization.
Andreas Maletti · 2011
These notes report on recent advances in the relatively new area of hyper-minimization. Several open questions that were raised in the pioneering article [Badr, Geffert, and Shipman. Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl., 43(1):69–94, 2009] are addressed here and the solutions, which are mostly taken from the literature, are presented in a uniform style. In particular, the most efficient hyper-minimization algorithms for several error profiles are presented and the languages of hyper-minimal automata are investigated.