{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T15:49:47Z","timestamp":1748360987965},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_169","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:55Z","timestamp":1330209535000},"page":"629-640","source":"Crossref","is-referenced-by-count":11,"title":["Minimal NFA problems are hard"],"prefix":"10.1007","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Ravikumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"49_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1973","unstructured":"Aho, A., J. Hopcroft and J. Ullman, The Design and Analysis of Computer Algorithms, 1973, Addison-Wesley, Reading, Massachusetts."},{"key":"49_CR2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M., \u2018Finite automata and unary languages', Theoretical Computer Science 47, 1986, 149\u2013158.","journal-title":"Theoretical Computer Science"},{"key":"49_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S., \u2018Complexity of theorem proving procedures', Proc. of 3rd Annual ACM Symp. on Theory of Computing, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"49_CR4","volume-title":"Computers and Intractability:A Guide to NP-Completeness","author":"M. Garey","year":"1978","unstructured":"Garey, M. and D. Johnson, Computers and Intractability:A Guide to NP-Completeness, 1978, Freeman, San Fransisco."},{"key":"49_CR5","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J. and J. Ullman, Introduction to Automata Theory, Languages and Computation, 1979, Addison-Wesley, Reading, Massachusetts."},{"key":"49_CR6","doi-asserted-by":"crossref","unstructured":"Hunt, H., \u2018On the time and tape complexity of languages', Proc. of 5th Annual ACM Symp. on Theory of Computing, 1973, 10\u201319.","DOI":"10.1145\/800125.804030"},{"key":"49_CR7","doi-asserted-by":"crossref","unstructured":"Hunt, H. and D. Rosenkrantz, \u2018Computational Parallels between regular and context-free languages', Proc. of 6th Annual ACM Symp. on Theory of Computing, 1974, 64\u201374.","DOI":"10.1145\/800119.803885"},{"key":"49_CR8","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"H. Hunt","year":"1976","unstructured":"Hunt H., D. Rosenkrantz and T. Szymanski, \u2018On the equivalence, containment and covering problems for the regular and context-free languages', Jl. of Comp. and Sys. Sciences 12, 1976, 222\u2013268.","journal-title":"Jl. of Comp. and Sys. Sciences"},{"key":"49_CR9","unstructured":"Jiang, T., E. McDowell and B. Ravikumar, \u2018The structure and complexity of minimal NFA's over a unary alphabet', University of Rhode Island Tech. Report, TR-200-90 (submitted)."},{"key":"49_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R., \u2018Reducibility among combinatorial problems', in R. E. Miller and J. W. Thatcher (eds.,), Complexity of Computer Computations, 1972, Plenum Press, NY, 85\u2013103."},{"key":"49_CR11","doi-asserted-by":"crossref","unstructured":"Kozen, D., \u2018Lower bounds for natural proof systems', Proc. of 18th Annual IEEE Symp. on FOCS, 1977, 254\u2013266.","DOI":"10.1109\/SFCS.1977.16"},{"key":"49_CR12","first-page":"183","volume":"5","author":"A. Mandel","year":"1978","unstructured":"Mandel, A. and I. Simon, \u2018On finite semi-groups of matrices', Theoretical Computer Science 5, 1978, 183\u2013204.","journal-title":"Theoretical Computer Science"},{"key":"49_CR13","first-page":"188","volume-title":"Proc. of 12th Annual IEEE Symp. on Switching and Auotmata Theory","author":"A. Meyer","year":"1971","unstructured":"Meyer, A., and M. Fischer, \u2018Economy of description by automata, grammars and formal systems', Proc. of 12th Annual IEEE Symp. on Switching and Auotmata Theory, 1971, IEEE Computer Society, Washington D.C., 188\u2013191."},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"Meyer, A., and L. Stockmeyer, \u2018The equivalence problem for regular expressions with squaring requires exponential space', Proc. of 13th Annual IEEE Symp. on Switching and Automata Theory, 1972, IEEE Computer Society, 125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"49_CR15","unstructured":"Myhill, J., \u2018Finite automata and the representation of events', WADD TR-57-624, 112\u2013137, 1957, Wright Patterson AFB, Ohio."},{"key":"49_CR16","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A. Nerode","year":"1958","unstructured":"Nerode, A., \u2018Linear automaton transformations', Proc. of AMS 9, 1958, 541\u2013544.","journal-title":"Proc. of AMS"},{"key":"49_CR17","volume-title":"These troisieme cycle","author":"C. Reutenauer","year":"1977","unstructured":"Reutenauer, C., \u2018Propietes arithmetiques et topologiques de series rationelles en variables noncommutatives', These troisieme cycle, 1977, Universit\u00e9 de Paris VI, Paris, France."},{"key":"49_CR18","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"Rabin, M. and D. Scott, \u2018Finite automata and their decision problems', IBM Journal of Res. and Development 3, 1959, 114\u2013125.","journal-title":"IBM Journal of Res. and Development"},{"key":"49_CR19","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"Ravikumar, B. and O. Ibarra, \u2018Relating the type of ambiguity to the succinctness of their representations', SIAM Journal on Computing 18, 1989, 1263\u20131282.","journal-title":"SIAM Journal on Computing"},{"key":"49_CR20","doi-asserted-by":"crossref","unstructured":"Rivest, R. and R. Schapire, \u2018Diversity-based inference of finite automata', Proc. of 28th Annual Symp. on FOCS, 1987, 78\u201387.","DOI":"10.1109\/SFCS.1987.21"},{"key":"49_CR21","unstructured":"Salomaa, A., Jewels of Formal Language Theory, 1981, Computer Science Press."},{"key":"49_CR22","unstructured":"Schapire, R., \u2018Diversity based inference of finite automata', Master's thesis, MIT Laboratory for Computer Science, May 1988. Tech. Report MIT\/LCS\/TR-413."},{"key":"49_CR23","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"R. Stearns","year":"1985","unstructured":"Stearns, R., and H. Hunt, \u2018On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata', SIAM Jl. on Computing 14, 1985, 598\u2013611.","journal-title":"SIAM Jl. on Computing"},{"key":"49_CR24","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. and A. Meyer, \u2018Word problems requiring exponential time\u2019 (prelim. report), Proc. of 5th Annual ACM symposium on Theory of Computing, 1973, 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"49_CR25","volume-title":"Set basis problem is NP-complete","author":"L. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L., \u2018Set basis problem is NP-complete', Report No. RC-5431, 1976, IBM Research Center, Yorktown Heights, NY."},{"issue":"6","key":"49_CR26","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K. Thompson","year":"1968","unstructured":"Thompson, K., \u2018Regular expression searching algorithm', Communications of ACM, 11:6, 1968, 419\u2013422.","journal-title":"Communications of ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_169.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:20Z","timestamp":1605646400000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_169","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}