Abstract
We introduce E-equivalence, which is a straightforward generalization of almost-equivalence. While almost-equivalence asks for ordinary equivalence up to a finite number of exceptions, in E-equivalence these exceptions or errors must belong to a (regular) set E. The computational complexity of minimization problems and their variants w.r.t. almost- and E-equivalence are studied. Roughly speaking, whenever nondeterministic finite automata (NFAs) are involved, most minimization problems, and their equivalence problems they are based on, become PSPACE-complete, while for deterministic finite automata (DFAs) the situation is more subtle. For instance, hyper-minimizing DFAs is NL-complete, but E-minimizing DFA s is NP-complete, even for finite E. The obtained results nicely fit to the known ones on ordinary minimization for finite automata. Moreover, since hyper-minimal and E-minimal automata are not necessarily unique (up to isomorphism as for minimal DFAs), we consider the problem of counting the number of these minimal automata. It turns out that counting hyper-minimal DFAs can be done in FP, while counting E-minimal DFA s is #P-hard, and belongs to the counting class #·coNP.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Àlvarez, C., Jenner, B.: A very hard log-space counting class. Theoret. Comput. Sci. 107(1), 3–30 (1993)
Badr, A.: Hyper-minimization in O(n 2). Internat. J. Found. Comput. Sci. 20(4), 735–746 (2009)
Badr, A., Geffert, V., Shipman, I.: Hyper-minimizing minimized deterministic finite state automata. RAIRO–Inform. Théori. Appl./Theoret. Inform. Appl. 43(1), 69–94 (2009)
Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43, 185–190 (1992)
Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inform. Comput. 97, 1–22 (1992)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman (1979)
Gawrychowski, P., Jeż, A.: Hyper-minimisation Made Efficient. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 356–368. Springer, Heidelberg (2009)
Gawrychowski, P., Jeż, A., Maletti, A.: On Minimising Automata with Errors. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 327–338. Springer, Heidelberg (2011)
Gold, E.M.: Complexity of automaton identification from given data. Inform. Control 37(3), 302–320 (1978)
Gruber, H., Holzer, M.: Finding Lower Bounds for Nondeterministic State Complexity Is Hard (Extended Abstract). In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 363–374. Springer, Heidelberg (2006)
Hemaspaandra, L.A., Vollmer, H.: The satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News 26(1), 2–13 (1995)
Holzer, M.: On emptiness and counting for alternating finite automata. In: Developments in Language Theory II (DLT); at the Crossroads of Mathematics, Computer Science and Biology, pp. 88–97. World Scientific (1996)
Holzer, M., Maletti, A.: An nlogn algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoret. Comput. Sci. 411(38-39), 3404–3413 (2010)
Hopcroft, J.: An nlogn algorithm for minimizing the state in a finite automaton. In: The Theory of Machines and Computations, pp. 189–196. Academic Press (1971)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)
Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), 935–938 (1988)
Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117–1141 (1993)
Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic log space. Math. Systems Theory 10, 1–17 (1976)
Ladner, R.E.: Polynomial space counting problems. SIAM J. Comput. 18(6), 1087–1097 (1989)
Maletti, A., Quernheim, D.: Optimal hyper-minimization. Internat. J. Found. Comput. Sci. 22(8), 1877–1891 (2011)
Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Switching and Automata Theory (SWAT), pp. 125–129. IEEE Society Press (1972)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)
Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform. 26(3), 279–284 (1988)
Szepietowski, A.: Closure properties of hyper-minimized automata. RAIRO–Inform. Théori. Appl./Theoret. Inform. Appl. 45(4), 459–466 (2011)
Toda, S.: Computational Complexity of Counting Complexity Classes. PhD thesis, Tokyo Institute of Technology, Department of Computer Science, Tokyo, Japan (1991)
Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189–201 (1979)
Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holzer, M., Jakobi, S. (2012). From Equivalence to Almost-Equivalence, and Beyond—Minimizing Automata with Errors. In: Yen, HC., Ibarra, O.H. (eds) Developments in Language Theory. DLT 2012. Lecture Notes in Computer Science, vol 7410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31653-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-31653-1_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31652-4
Online ISBN: 978-3-642-31653-1
eBook Packages: Computer ScienceComputer Science (R0)