{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:32:54Z","timestamp":1754195574614},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_28","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"315-326","source":"Crossref","is-referenced-by-count":5,"title":["Lower Bounds for the Transition Complexity of NFAs"],"prefix":"10.1007","author":[{"given":"Michael","family":"Domaratzki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","volume-title":"Combinatorial Designs, Construction Methods","author":"I. Anderson","year":"1990","unstructured":"Anderson, I.: Combinatorial Designs, Construction Methods. John Wiley, Chichester (1990)"},{"key":"28_CR2","volume-title":"Combinatorics: Topics, Techniques, Algorithms","author":"P.J. Cameron","year":"1996","unstructured":"Cameron, P.J.: Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge (1996)"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. Queen\u2019s School of Computing Technical Report No. 2006-515, Available at www.cs.queensu.ca\/TechReports","DOI":"10.1007\/11821069_28"},{"key":"28_CR4","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. Inform. Proc. Lett.\u00a059, 75\u201377 (1996)","journal-title":"Inform. Proc. Lett."},{"key":"28_CR5","first-page":"193","volume":"8","author":"J. Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Universal Comput. Sci.\u00a08, 193\u2013234 (2002)","journal-title":"J. Universal Comput. Sci."},{"key":"28_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-540-31856-9_33","volume-title":"STACS 2005","author":"G. Gramlich","year":"2005","unstructured":"Gramlich, G., Schnitger, G.: Minimizing NFA\u2019s and regular expressions. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 399\u2013411. Springer, Heidelberg (2005)"},{"key":"28_CR7","unstructured":"Gruber, H., Holzer, M.: A note on the number of transitions of nondeterministic finite automata. In: Fernau, H. (ed.) 15. Theorietag der GI-Fachgruppe 0.1.5. Automaten und Formale Sprachen, pp. 24\u201325 (2005)"},{"key":"28_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/11779148_33","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2006","unstructured":"Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 363\u2013374. Springer, Heidelberg (2006)"},{"key":"28_CR9","unstructured":"Gruber, H., Holzer, M.: Results on the average state complexity of finite automata accepting finite languages. In: Proc. of Descriptional Complexity of Formal Systems, DCFS 2006 (to appear)"},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-45005-X_14","volume-title":"Developments in Language Theory","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Unary language operations and their nondeterministic state complexity. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol.\u00a02450, pp. 162\u2013172. Springer, Heidelberg (2003)"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1142\/S0129054103002199","volume":"14","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Internat. J. Foundations of Computer Science\u00a014, 1087\u20131102 (2003)","journal-title":"Internat. J. Foundations of Computer Science"},{"key":"28_CR12","doi-asserted-by":"crossref","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)"},{"key":"28_CR13","first-page":"519","volume":"7","author":"J. Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J.: Descriptional complexity of finite automata: Concepts and open problems. J. Automata, Languages and Combinatorics\u00a07, 519\u2013531 (2002)","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/11523468_32","volume-title":"Automata, Languages and Programming","author":"J. Hromkovi\u010d","year":"2005","unstructured":"Hromkovi\u010d, J., Schnitger, G.: NFAs with and without \u03b5-transitions. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 385\u2013396. Springer, Heidelberg (2005)"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J. Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Seibert, S., Wilke, T.: Translating regular expressions in small \u03b5-free nondeterministic finite automata. J. Comput. System Sci.\u00a062, 565\u2013588 (2001)","journal-title":"J. Comput. System Sci."},{"key":"28_CR16","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 J. Comput.\u00a022, 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"28_CR17","series-title":"EATCS Texts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal Combinatorics with Applications in Computer Science","author":"S. Jukna","year":"2001","unstructured":"Jukna, S.: Extremal Combinatorics with Applications in Computer Science. EATCS Texts in Theoretical Computer Science. Springer, Heidelberg (2001)"},{"key":"28_CR18","unstructured":"Kari, J.: Personal communication (April 2006)"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(02)00436-2","volume":"85","author":"Y.. Lifshits","year":"2003","unstructured":"Lifshits, Y.: A lower bound on the size of \u03b5-free NFA corresponding to a regular expression. Inform. Proc. Lett.\u00a085, 293\u2013299 (2003)","journal-title":"Inform. Proc. Lett."},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.tcs.2004.03.070","volume":"327","author":"A. Malcher","year":"2004","unstructured":"Malcher, A.: Minimizing finite automata is computationally hard. Theoret. Comput. Sci.\u00a0327, 375\u2013390 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR21","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0I, pp. 41\u2013110. Springer, Heidelberg (1997)"},{"key":"28_CR22","first-page":"142","volume":"76","author":"S. Yu","year":"2002","unstructured":"Yu, S.: State complexity of finite and infinite regular languages. Bulletin of the EATCS\u00a076, 142\u2013152 (2002)","journal-title":"Bulletin of the EATCS"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:16:32Z","timestamp":1605644192000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11821069_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}