{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T00:28:44Z","timestamp":1777508924859,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642316227","type":"print"},{"value":"9783642316234","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31623-4_20","type":"book-chapter","created":{"date-parts":[[2012,7,9]],"date-time":"2012-07-09T05:03:34Z","timestamp":1341810214000},"page":"252-265","source":"Crossref","is-referenced-by-count":8,"title":["State Complexity and Limited Nondeterminism"],"prefix":"10.1007","author":[{"given":"Alexandros","family":"Palioudakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Selim G.","family":"Akl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","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, Inform. Process. Lett.\u00a043, 185\u2013190 (1992)","journal-title":"Process. Lett."},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.jcss.2011.03.001","volume":"78","author":"H. Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, H., Martens, W.: The tractability frontier for NFA minimization. J. Comput. System Sci.\u00a078, 198\u2013210 (2012)","journal-title":"J. Comput. System Sci."},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci.\u00a047, 149\u2013158 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"20_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. Inf. Proc. Lett.\u00a059, 75\u201377 (1996)","journal-title":"Inf. Proc. Lett."},{"key":"20_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. Univ. Comput. Sci.\u00a08, 193\u2013234 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0890-5401(90)90053-K","volume":"86","author":"J. Goldstine","year":"1990","unstructured":"Goldstine, J., Kintala, C.M.R., Wotschke, D.: On measuring nondeterminism in regular languages. Inform. Comput.\u00a086, 179\u2013194 (1990)","journal-title":"Inform. Comput."},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0890-5401(92)90014-7","volume":"100","author":"J. Goldstine","year":"1992","unstructured":"Goldstine, J., Leung, H., Wotschke, D.: On the relation between ambiguity and nondeterminism in finite automata. Inform. Comput.\u00a0100, 261\u2013270 (1992)","journal-title":"Inform. Comput."},{"key":"20_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":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73208-2_21","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M.: Inapproximability of Nondeterministic State and Transition Complexity Assuming P \u2260 NP. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 205\u2013216. Springer, Heidelberg (2007)"},{"key":"20_CR10","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 Comput. Sci.\u00a014, 1087\u20131102 (2003)","journal-title":"Internat. J. Foundations of Comput. Sci."},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M. Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata \u2014 A survey. Inf. Comput.\u00a0209, 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"20_CR12","first-page":"453","volume":"6","author":"M. Holzer","year":"2001","unstructured":"Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. J. Automata, Languages and Combinatorics\u00a06, 453\u2013466 (2001)","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"J. Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J., Seibert, S., Karhum\u00e4ki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Inform. Comput.\u00a0172, 202\u2013217 (2002)","journal-title":"Inform. Comput."},{"key":"20_CR14","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 NFA\u2019s over a unary alphabet. Internat. J. Foundations Comput. Sci.\u00a02, 163\u2013182 (1991)","journal-title":"Internat. J. Foundations Comput. Sci."},{"key":"20_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. Comput.\u00a022, 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"20_CR16","first-page":"269","volume":"5","author":"M. Kappes","year":"2000","unstructured":"Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states. J. Automata, Languages, and Combinatorics\u00a05, 269\u2013278 (2000)","journal-title":"J. Automata, Languages, and Combinatorics"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF00263994","volume":"13","author":"C.M.R. Kintala","year":"1980","unstructured":"Kintala, C.M.R., Wotschke, D.: Amounts of nondeterminism in finite automata. Acta Inform.\u00a013, 199\u2013204 (1980)","journal-title":"Acta Inform."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Leung, H.: Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM J. Comput, 1073\u20131082 (1998)","DOI":"10.1137\/S0097539793252092"},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1142\/S0129054105003418","volume":"16","author":"H. Leung","year":"2005","unstructured":"Leung, H.: Descriptional complexity of NFA of different ambiguity. Internat. J. Foundations Comput. Sci.\u00a016, 975\u2013984 (2005)","journal-title":"Internat. J. Foundations Comput. Sci."},{"key":"20_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":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/978-3-642-15155-2_49","volume-title":"Mathematical Foundations of Computer Science 2010","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Unambiguous Finite Automata over a Unary Alphabet. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 556\u2013567. Springer, Heidelberg (2010)"},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput.\u00a018, 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Schmidt, E.M.: Succinctness of description of context-free, regular and unambiguous languages. Ph.D. thesis, Cornell University (1978)","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511808876"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0214044","volume":"14","author":"R. Stearns","year":"1985","unstructured":"Stearns, R., Hunt, H.: On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM J. Comput.\u00a014, 596\u2013611 (1985)","journal-title":"SIAM J. Comput."},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0I, pp. 41\u2013110. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S. Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoret. Comput. Sci.\u00a0125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31623-4_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:40:37Z","timestamp":1620128437000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31623-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316227","9783642316234"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31623-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}