{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T13:41:59Z","timestamp":1771854119151,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319192246","type":"print"},{"value":"9783319192253","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19225-3_4","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"46-57","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Nondeterministic Tree Width of Regular Languages"],"prefix":"10.1007","author":[{"given":"Cezar","family":"C\u00e2mpeanu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"JC Birget","year":"1992","unstructured":"Birget, J.C.: Intersection and union of regular languages and state complexity. Inf. Process. Lett. 43, 185\u2013190 (1992)","journal-title":"Inf. Process. Lett."},{"key":"4_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. Syst. Sci. 78, 198\u2013210 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1006\/inco.1997.2695","volume":"142\u20132","author":"A Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inf. Comput. 142\u20132, 182\u2013206 (1998)","journal-title":"Inf. Comput."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"162","DOI":"10.4204\/EPTCS.151.11","volume":"151\u2013AFL","author":"C C\u00e2mpeanu","year":"2014","unstructured":"C\u00e2mpeanu, C.: Simplyfying nondeterministic finite cover automata. Electron. Proc. Theoret. Comput. Sci. 151\u2013AFL, 162\u2013173 (2014)","journal-title":"Electron. Proc. Theoret. Comput. Sci."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.7561\/SACS.2015.1.3","volume":"29","author":"C C\u00e2mpeanu","year":"2015","unstructured":"C\u00e2mpeanu, C.: Non-deterministic finite cover automata. Sci. Ann. Comput. Sci. 29, 3\u201328 (2015)","journal-title":"Sci. Ann. Comput. Sci."},{"key":"4_CR6","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. 47, 149\u2013158 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0021-8693(69)90070-2","volume":"13","author":"S Eilenberg","year":"1969","unstructured":"Eilenberg, S., Sch\u00fctzenberger, M.P.: Rational sets in commutative monoids. J. Algebra 13(2), 173\u2013191 (1969)","journal-title":"J. Algebra"},{"key":"4_CR8","unstructured":"Ellul, K.: Descriptional Complexity Measures of Regular Languages. Master\u2019s thesis, University of Waterloo (2004)"},{"key":"4_CR9","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A review on state complexity of individual operations. Faculdade de Ciencias, Universidade do Porto, Technical report DCC-2011-8. www.dcc.fc.up.pt\/dcc\/Pubs\/TReports\/TR11\/dcc-2011-08.pdf To appear in Computer Science Review"},{"key":"4_CR10","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. Inf. Comput. 86, 179\u2013194 (1990)","journal-title":"Inf. Comput."},{"key":"4_CR11","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. 4036, pp. 363\u2013374. Springer, Heidelberg (2006). http:\/\/dx.doi.org\/10.1007\/11779148_33"},{"key":"4_CR12","unstructured":"Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: Proceedings of LATA, pp. 261\u2013272 (2007)"},{"key":"4_CR13","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. Int. J. Found. Comput. Sci. 14, 1087\u20131102 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR14","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. Inf. Comput. 172, 202\u2013217 (2002)","journal-title":"Inf. Comput."},{"key":"4_CR15","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. Int. J. Found. Comput. Sci. 2, 163\u2013182 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_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. 22, 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"4_CR18","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. Int. J. Found. Comput. Sci. 16, 975\u2013984 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR19","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. 327, 375\u2013390 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-642-31623-4_20","volume-title":"Descriptional Complexity of Formal Systems","author":"A Palioudakis","year":"2012","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity and limited nondeterminism. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 252\u2013265. Springer, Heidelberg (2012)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/978-3-319-04298-5_39","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"A Palioudakis","year":"2014","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Unary NFAs with limited nondeterminism. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 443\u2013454. Springer, Heidelberg (2014)"},{"issue":"2\u20134","key":"4_CR22","first-page":"245","volume":"17","author":"A Palioudakis","year":"2012","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity of finite tree width NFAs. J. Automata Lang. Comb. 17(2\u20134), 245\u2013264 (2012)","journal-title":"J. Automata Lang. Comb."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Palioudakis, A.: State complexity of nondeterministic finite automata with limited nondeterminism. Ph.D. thesis, Queen\u2019s University (2014)","DOI":"10.1007\/978-3-319-09704-6_29"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.H.: Relating the degree of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18, 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"key":"4_CR25","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2009","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings of the 5th Symposium on Theory of Computing, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"4_CR27","doi-asserted-by":"publisher","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. I, pp. 41\u2013110. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19225-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T13:15:41Z","timestamp":1674566141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}