World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue Implementation and Application of Automata (CIAA 2010)No Access

OPTIMAL HYPER-MINIMIZATION

    https://doi.org/10.1142/S0129054111009094Cited by:9 (Source: Crossref)

    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

    • A. Badr, Int. J. Found. Comput. Sci. 20, 735 (2009), DOI: 10.1142/S012905410900684X. Link, Web of ScienceGoogle Scholar
    • A. Badr, V. Geffert and I. Shipman, RAIRO Theor. Inf. Appl. 43, 69 (2009), DOI: 10.1051/ita:2007061. Crossref, Web of ScienceGoogle 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 ) . CrossrefGoogle 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 Scholar
    • T. 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
    • M. Holzer and A. Maletti, Theor. Comput. Sci. 411, 3404 (2010), DOI: 10.1016/j.tcs.2010.05.029. Crossref, Web of ScienceGoogle Scholar
    • J. E. Hopcroft, Theory of Machines and Computations (Academic Press, 1971) pp. 189–196. CrossrefGoogle 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 ) . CrossrefGoogle Scholar
    • M. Mohri, Comput. Linguist. 23, 269 (1997). Web of ScienceGoogle 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 Scholar
    • D. 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
    • S. Yu, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer, 1997) pp. 41–110. CrossrefGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science