{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T02:11:54Z","timestamp":1792807914259,"version":"4.5.0"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1993,12]]},"abstract":"<jats:p>Finite automata (FA\u2019s) are of fundamental importance in theory and in applications. The following basic minimization problem is studied: Given a DFA (deterministic FA), find a minimum equivalent nondeterministic FA (NFA). This paper shows that the natural decision problem associated with it is PSPACE-complete. More generally, let ${\\text{A}} \\to {\\text{B}}$ denote the problem of converting a given FA of type A to a minimum FA of type B. This paper also shows that most of these problems are computationally hard. Motivated by the question of how much nondeterminism suffices to make the decision problem involving an NFA computationally hard, the authors study the complexity decision problems for FA\u2019s and present several intractability results, even for cases in which the input is deterministic or nondeterministic with a very limited nondeterminism. For example, it is shown that it is PSPACE-complete to decide if $L(M_1 ) \\cdot L(M_2 ) = L(M_3 )$, where $M_1 $, $M_2 $, and $M_3 $ are DFAs. These problems are related to some classical problems in automata theory (such as deciding whether an FA has the finite power property), as well as recent ones (such as determining the diversity of a given FA).<\/jats:p>","DOI":"10.1137\/0222067","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:56Z","timestamp":1109227136000},"page":"1117-1141","source":"Crossref","is-referenced-by-count":175,"title":["Minimal NFA Problems are Hard"],"prefix":"10.1137","volume":"22","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"Ravikumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. Cook,  Complexity of theorem proving procedures,  Proc. 3rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1971,  151\u2013158 0253.68020","DOI":"10.1145\/800157.805047"},{"key":"R3","volume-title":"Computers and intractability","author":"Garey M.","year":"1979"},{"key":"R4","volume-title":"Algebraic theory of automata","author":"Ginzburg Abraham","year":"1968"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)90562-4"},{"key":"R6","volume-title":"Algebraic structure theory of sequential machines","author":"Hartmanis J.","year":"1966"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"R8","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft J.","year":"1979"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"H. Hunt,  On the time and tape complexity of languages. I,  Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York,  1973,  10\u201319 54:91500357.68090","DOI":"10.1145\/800125.804030"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"H. Hunt, D. Rosenkrantz,  Computational parallels between the regular and context-free languages,  Sixth Annual ACM Symposium on Theory of Computing (Seattle, Wash., 1974), Assoc. Comput. Mach., New York,  1974,  64\u201374 55:18410357.68091","DOI":"10.1145\/800119.803885"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80038-4"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1142\/S012905419100011X"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Dexter Kozen,  Lower bounds for natural proof systems,  18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), IEEE Comput. Sci., Long Beach, Calif.,  1977,  254\u2013266, Washington, DC 58:13931","DOI":"10.1109\/SFCS.1977.16"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90001-9"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Meyer, M. Fischer,  Economy of description by automata, grammars and formal systems,  Proc. 12th Annual IEEE Symposium on Switching and Automata Theory, IEEE Computer Society, Washington, DC,  1971,  188\u2013191","DOI":"10.1109\/SWAT.1971.11"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Meyer, L. Stockmeyer,  The equivalence problem for regular expressions with squaring requires exponential space,  Proc. 13th Annual IEEE Symposium on Switching and Automata Theory, IEEE Computer Society, Washington, DC,  1972,  125\u2013129","DOI":"10.1109\/SWAT.1972.29"},{"key":"R18","unstructured":"J. Myhill,  Finite automata and the representation of events, Tech. Report, WADD TR-57-624, Wright Patterson AFB, OH,  1957, pp. 112\u2013137"},{"key":"R19","volume-title":"Machine learning","author":"Natarajan B.","year":"1991"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0135681-9"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"L. Pitt, M. Warmuth,  The minimum consistent DFA problem cannot be approximated within any polynomial,  Proc. 21st Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1989,  421\u2013432","DOI":"10.1145\/73007.73048"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"key":"R24","unstructured":"C. Reutenauer, Masters Thesis,  Propri\u00e9t\u00e9s arithmetiques et topologiques de s\u00e9ries rationelles en variables noncommutatives, Th\u00e8se troisi\u00e8me cycle, Universite de Paris VI, Paris,  1977"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"R. Rivest, R. Schapire,  Diversity-based inference of finite automata,  Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1987,  78\u201387","DOI":"10.1109\/SFCS.1987.21"},{"key":"R26","volume-title":"Jewels of formal language theory","author":"Salomaa Arto","year":"1981"},{"key":"R27","unstructured":"R. Schapire,  Diversity Based Inference on Finite Automata, Tech. Report, MIT\/LCS\/TR-413, MIT Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA,  1988, master's thesis"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0214044"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer, A. Meyer,  Word problems requiring exponential time: preliminary report,  Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York,  1973,  1\u20139 54:65570359.68050","DOI":"10.1145\/800125.804029"},{"key":"R30","unstructured":"L. Stockmeyer,  Set Basis Problem is NP-Complete, Report, RC-5431, IBM T. J. Watson Research Center, Yorktown Heights, NY,  1976"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"W. Tzeng,  The equivalence and learning of probabilistic automata,  Proc. 30th Annual IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1989,  268\u2013273","DOI":"10.1109\/SFCS.1989.63489"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0222067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:54:58Z","timestamp":1787338498000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0222067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["10.1137\/0222067"],"URL":"https:\/\/doi.org\/10.1137\/0222067","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}