OPTIMAL HYPER-MINIMIZATION
Abstract
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Ż: 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.
This is an extended and revised version of [A. Maletti: Better hyper-minimization — not as fast, but fewer errors. In Proc. CIAA, volume 6482 of LNCS, pages 201-210. Springer-Verlag, 2011].
References
- Int. J. Found. Comput. Sci. 20, 735 (2009), DOI: 10.1142/S012905410900684X. Link, Web of Science, Google Scholar
- RAIRO Theor. Inf. Appl. 43, 69 (2009), DOI: 10.1051/ita:2007061. Crossref, Web of Science, Google Scholar
- J. Berstel, L. Boasson, O. Carton and I. Fagnot, "Minimization of automata" 2010. Manuscript available at , arxiv: 1010.5318 . Google Scholar
-
B. Bollobás , Random graphs ( Cambridge University Press , 2001 ) . Crossref, Google Scholar - D. Eppstein, "Finding common ancestors and disjoint paths in DAGs" Tech. Rep. 95-52, University of California, Irvine, 1995 . Google Scholar
P. Gawrychowski and A. Jeż , Hyper-minimisation made efficient, Proc. 34th Int. Symp. Mathematical Foundations of Computer Science5734,LNCS (Springer, 2009) pp. 356–368. Google ScholarT. Hanneforth , fsm2 — A scripting language interpreter for manipulating weighted finite-state automata, Proc. 8th Int. Workshop Finite-State Methods and Natural Language Processing6062,LNCS (Springer, 2009) pp. 13–30. Google Scholar- Theor. Comput. Sci. 411, 3404 (2010), DOI: 10.1016/j.tcs.2010.05.029. Crossref, Web of Science, Google Scholar
J. E. Hopcroft , Theory of Machines and Computations (Academic Press, 1971) pp. 189–196. Crossref, Google Scholar-
J. E. Hopcroft , R. Motwani and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation , 3rd edn. ( Addison Wesley , 2007 ) . Google Scholar -
C. D. Johnson , Formal Aspects of Phonological Description ( De Gruyter , 1972 ) . Crossref, Google Scholar - Comput. Linguist. 23, 269 (1997). Web of Science, Google Scholar
S. Schewe , Beyond hyper-minimisation—minimising DBAs and DPAs is NP-complete, Proc. IARCS Ann. Conf. Foundations of Software Technology and Theoretical Computer Science8,LIPIcs (Schloss Dagstuhl, 2010) pp. 400–411. Google ScholarD. Tabakov and M. Y. Vardi , Experimental evaluation of classical automata constructions, Proc. 12th Int. Conf. Logic for Programming, Artificial Intelligence, and Reasoning3835,LNCS (Springer, 2005) pp. 396–411. Google Scholar- Handbook of Formal Languages 1, eds.
G. Rozenberg and A. Salomaa (Springer, 1997) pp. 41–110. Crossref, Google Scholar ,
Remember to check out the Most Cited Articles! |
---|
Check out these Handbooks in Computer Science |