{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T17:53:36Z","timestamp":1776880416324,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540732075","type":"print"},{"value":"9783540732082","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73208-2_6","type":"book-chapter","created":{"date-parts":[[2007,9,12]],"date-time":"2007-09-12T07:58:11Z","timestamp":1189583891000},"page":"31-35","source":"Crossref","is-referenced-by-count":9,"title":["Descriptional Complexity of Nondeterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Kai","family":"Salomaa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(93)90160-U","volume":"119","author":"J.-C. Birget","year":"1993","unstructured":"Birget, J.-C.: Partial orders on words, minimal elements of regular languages and state complexity. Theoret. Comput. Sci.\u00a0119, 267\u2013291 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR2","unstructured":"Domaratzki, M., Salomaa, K.: Transition complexity of language operations. In: Leung, H., Pighizzini, G. (eds.): Proc. of Descriptional Complexity of Formal Systems, DCFS 2006, Las Cruces, NM, pp. 141\u2013152 (2006)"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11821069_28","volume-title":"Mathematical Foundations of Computer Science 2006","author":"M. Domaratzki","year":"2006","unstructured":"Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 315\u2013326. Springer, Heidelberg (2006)"},{"key":"6_CR4","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 Computer Science\u00a08, 193\u2013234 (2002)","journal-title":"J. Universal Computer Science"},{"key":"6_CR5","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. Inf. Proc. Letters\u00a059, 75\u201377 (1996)","journal-title":"Inf. Proc. Letters"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"6_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":"6_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: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 363\u2013374. Springer, Heidelberg (2006)"},{"key":"6_CR9","unstructured":"Gruber, H., Holzer, M.: Results on the average state complexity of finite automata accepting finite languages. In: Leung, H., Pighizzini, G. (eds.) Proc. of Descriptional Complexity of Formal Systems, DCFS 2006, Las Cruces, NM, pp. 267\u2013275 (2006)"},{"key":"6_CR10","unstructured":"Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: Proc. of 1st International Conference on Language Theory and Applications, LATA (2007)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming P\u2009\u2260\u2009NP. In: Proc. of 11th International Conference Developments in Language Theory, DLT (2007)","DOI":"10.1007\/978-3-540-73208-2_21"},{"key":"6_CR12","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":"6_CR13","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":"6_CR14","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":"6_CR15","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. Computing\u00a022, 1117\u20131141 (1993)","journal-title":"SIAM J. Computing"},{"key":"6_CR16","unstructured":"Kari, J.: Personal communication (2006)"},{"key":"6_CR17","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":"6_CR18","doi-asserted-by":"crossref","unstructured":"Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoret. Comput. Sci. (to appear)","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Salomaa, K., Yu, S.: On the state complexity of combined operations and their estimation. Internat. J. Foundations of Computer Science (to appear)","DOI":"10.1142\/S0129054107004917"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11672142_35","volume-title":"STACS 2006","author":"G. Schnitger","year":"2006","unstructured":"Schnitger, G.: Regular expressions and NFAs without \u03b5-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 432\u2013443. Springer, Heidelberg (2006)"},{"key":"6_CR21","unstructured":"Yu, S.: Grail+: A symbolic computation environment for finite-state machines, regular expressions and finite languages (2002), http:\/\/www.csd.uwo.ca\/Research\/grail"},{"key":"6_CR22","first-page":"221","volume":"6","author":"S. Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Automata, Languages and Combinatorics\u00a06, 221\u2013234 (2001)","journal-title":"J. Automata, Languages and Combinatorics"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73208-2_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:12:29Z","timestamp":1605762749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73208-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540732075","9783540732082"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73208-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}