{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T15:48:51Z","timestamp":1775404131873,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540354284","type":"print"},{"value":"9783540354307","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11779148_33","type":"book-chapter","created":{"date-parts":[[2006,6,21]],"date-time":"2006-06-21T05:55:49Z","timestamp":1150869349000},"page":"363-374","source":"Crossref","is-referenced-by-count":25,"title":["Finding Lower Bounds for Nondeterministic State Complexity Is Hard"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","unstructured":"Adorna, H.N.: Some descriptional complexity problems in finite automata theory. In: Salda\u00f1a, R.P., Chua, C. (eds.) Proceedings of the 5th Philippine Computing Science Congress, Cebu City, Philippines, March 2005, pp. 27\u201332. Computing Society of the Philippines (2005)"},{"key":"33_CR2","unstructured":"Bezrukov, S., Fron\u010dek, D., Rosenberg, S.J., Kov\u00e1\u0159, P.: On biclique coverings (preprint, 2005)"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"J.-C. Birget","year":"1992","unstructured":"Birget, J.-C.: Intersection and union of regular languages and state complexity. Information Processing Letters\u00a043, 185\u2013190 (1992)","journal-title":"Information Processing Letters"},{"key":"33_CR4","series-title":"MRI Symposia Series","first-page":"529","volume-title":"Canonical Regular Expressions and Minimal State Graphs for Definite Events","author":"J.A. Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Mathematical theory of automata. In: Canonical Regular Expressions and Minimal State Graphs for Definite Events. MRI Symposia Series, vol.\u00a012, pp. 529\u2013561. Polytechnic Press, NY (1962)"},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K. Cameron","year":"1989","unstructured":"Cameron, K.: Induced matchings. Discrete Applied Mathematics\u00a024, 97\u2013102 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0020-0190(96)00095-6","volume":"59","author":"I. Glaister","year":"1996","unstructured":"Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters\u00a059, 75\u201377 (1996)","journal-title":"Information Processing Letters"},{"key":"33_CR7","volume-title":"Formal Languages and Their Relation to Automata","author":"J.E. Hopcroft","year":"1968","unstructured":"Hopcroft, J.E., Ullman, J.D.: Formal Languages and Their Relation to Automata. Addison-Wesley, Reading (1968)"},{"key":"33_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03442-2","volume-title":"Communication Complexity and Parallel Computing","author":"J. Hromkovi\u010d","year":"1997","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)"},{"issue":"4","key":"33_CR9","first-page":"519","volume":"7","author":"J. Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J.: Descriptional complexity of finite automata: Concepts and open problems. Journal of Automata, Languages and Combinatorics\u00a07(4), 519\u2013531 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Karhum\u00e4ki, J., Klauck, H., Schnitger, G., Seibert, S.: Measures of nondeterminism in finite automata. Report TR00-076, Electronic Colloquium on Computational Complexity (ECCC) (2000)","DOI":"10.1007\/3-540-45022-X_17"},{"issue":"2","key":"33_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S012905419100011X","volume":"2","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFAs over a unary alphabet. International Journal of Foundations of Computer Science\u00a02(2), 163\u2013182 (1991)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"6","key":"33_CR12","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM Journal on Computing\u00a022(6), 1117\u20131141 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR13","series-title":"Topics in Computer Mathematics","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1201\/9780203009642.ch16","volume-title":"Grammars and Automata for String Processing","author":"G. Jir\u00e1skov\u00e1","year":"2003","unstructured":"Jir\u00e1skov\u00e1, G.: Note on minimal automata and uniform communication protocols. In: Mart\u00edn-Vide, C., Mitrana, V. (eds.) Grammars and Automata for String Processing. Topics in Computer Mathematics, vol.\u00a09, pp. 163\u2013170. Taylor and Francis, Abington (2003)"},{"issue":"7","key":"33_CR14","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1109\/T-C.1970.222994","volume":"C-19","author":"T. Kameda","year":"1970","unstructured":"Kameda, T., Weiner, P.: On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers\u00a0C-19(7), 617\u2013627 (1970)","journal-title":"IEEE Transactions on Computers"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C-20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transaction on Computing\u00a0C-20, 1211\u20131219 (1971)","journal-title":"IEEE Transaction on Computing"},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development\u00a03, 114\u2013125 (1959)","journal-title":"IBM Journal of Research and Development"},{"issue":"2\u20133","key":"33_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2004.02.032","volume":"320","author":"A. Salomaa","year":"2004","unstructured":"Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theoretical Computer Science\u00a0320(2\u20133), 315\u2013329 (2004)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11779148_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:15:53Z","timestamp":1619507753000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11779148_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354284","9783540354307"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11779148_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}