{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T09:56:42Z","timestamp":1725530202217},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642009815"},{"type":"electronic","value":"9783642009822"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00982-2_5","type":"book-chapter","created":{"date-parts":[[2009,3,30]],"date-time":"2009-03-30T19:51:54Z","timestamp":1238442714000},"page":"59-70","source":"Crossref","is-referenced-by-count":1,"title":["State Complexity of Nested Word Automata"],"prefix":"10.1007","author":[{"given":"Kai","family":"Salomaa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R.: Marrying words and trees. In: Proc. of 26th ACM Symposium on Principles of Database Systems, PODS 2007, pp. 233\u2013242 (2007)","DOI":"10.1145\/1265530.1265564"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Arenas, M., Barcel\u00f3, P., Etessami, K., Immerman, N., Libkin, L.: First-order and temporal logics for nested words. In: Proc. of 22nd IEEE Symposium on Logic in Computer Science, pp. 151\u2013160 (2007)","DOI":"10.1109\/LICS.2007.19"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1102","DOI":"10.1007\/11523468_89","volume-title":"Automata, Languages and Programming","author":"R. Alur","year":"2005","unstructured":"Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1102\u20131114. Springer, Heidelberg (2005)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11779148_1","volume-title":"Developments in Language Theory","author":"R. Alur","year":"2006","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 1\u201313. Springer, Heidelberg (2006)"},{"key":"5_CR5","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. Full version of [4], www.cis.upenn.edu\/~alur\/Stoc04Dlt06.pdf"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1007\/978-3-540-73420-8_76","volume-title":"Automata, Languages and Programming","author":"M. Arenas","year":"2007","unstructured":"Arenas, M., Barcel\u00f3, P., Libkin, L.: Regular languages of nested words: Fixed points, automata, and synchronization. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 888\u2013900. Springer, Heidelberg (2007)"},{"key":"5_CR7","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":"Inform. Process. Lett."},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-540-74456-6_14","volume-title":"Mathematical Foundations of Computer Science 2007","author":"P. Chervet","year":"2007","unstructured":"Chervet, P., Walukiewicz, I.: Minimizing variants of visibly pushdown automata. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 135\u2013146. Springer, Heidelberg (2007)"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1016\/j.jcss.2008.02.007","volume":"74","author":"M. Domaratzki","year":"2008","unstructured":"Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. J. Comput. System. Sci.\u00a074, 1116\u20131130 (2008)","journal-title":"J. Comput. System. Sci."},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2007.07.034","volume":"387","author":"M. Domaratzki","year":"2007","unstructured":"Domaratzki, M., Salomaa, K.: Transition complexity of language operations. Theoret. Comput. Sci.\u00a0387, 147\u2013154 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR11","first-page":"75","volume":"83","author":"Y. Gao","year":"2008","unstructured":"Gao, Y., Salomaa, K., Yu, S.: The state complexity of two combined operations: Star of catenation and star of reversal. Fund. Inform.\u00a083, 75\u201389 (2008)","journal-title":"Fund. Inform."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ipl.2008.08.002","volume":"109","author":"O. Gauwin","year":"2008","unstructured":"Gauwin, O., Niehren, J., Roos, Y.: Streaming tree automata. Inform. Proc. Lett.\u00a0109, 13\u201317 (2008)","journal-title":"Inform. Proc. Lett."},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree languages. In: [27], vol.\u00a0III, pp. 1\u201368","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"5_CR14","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. Process. Lett.\u00a059, 75\u201377 (1996)","journal-title":"Inform. Process. Lett."},{"key":"5_CR15","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":"5_CR16","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":"5_CR17","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\u2009\u2260\u2009NP. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 205\u2013216. Springer, Heidelberg (2007)"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Han, Y.-S., Salomaa, K.: Nondeterministic state complexity of nested word automata (September 2008) (submitted for publication)","DOI":"10.1007\/978-3-642-00982-2_5"},{"key":"5_CR19","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":"5_CR20","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)"},{"key":"5_CR21","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":"5_CR22","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.tcs.2004.04.011","volume":"330","author":"G. Jir\u00e1skov\u00e1","year":"2005","unstructured":"Jir\u00e1skov\u00e1, G.: State complexity of some operations on binary regular languages. Theoret. Comput. Sci.\u00a0330, 287\u2013298 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/11817949_14","volume-title":"CONCUR 2006 \u2013 Concurrency Theory","author":"V. Kumar","year":"2006","unstructured":"Kumar, V., Madhusudan, P., Viswanathan, M.: Minimization, learning, and conformance testing of boolean programs. In: Baier, C., Hermanns, H. (eds.) CONCUR 2006. LNCS, vol.\u00a04137, pp. 203\u2013217. Springer, Heidelberg (2006)"},{"key":"5_CR24","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of nested word automata. In: C\u00e2mpeanu, C., Pighizzini, G. (eds.) Descriptional Complexity of Formal Systems, DCFS 2008, Charlottetown, Canada, pp. 194\u2013206 (2008)"},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-540-49382-2_12","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"A. Neumann","year":"1998","unstructured":"Neumann, A., Seidl, H.: Locating matches of tree patterns in forests. In: Arvind, V., Ramanujam, R. (eds.) FST TCS 1998. LNCS, vol.\u00a01530, pp. 134\u2013146. Springer, Heidelberg (1998)"},{"key":"5_CR26","unstructured":"Nguyen, H.: VPAlib: Visibly pushdown automata library (2006), http:\/\/www.emn.fr\/x-info\/hnguyen\/vpa"},{"volume-title":"Handbook of Formal Languages","year":"1997","key":"5_CR27","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol.\u00a0I\u2013III. Springer, Heidelberg (1997)"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1142\/S0129054107004917","volume":"18","author":"K. Salomaa","year":"2007","unstructured":"Salomaa, K., Yu, S.: On the state complexity of combined operations and their estimation. Internat. J. Foundations of Comput. Sci.\u00a018, 683\u2013698 (2007)","journal-title":"Internat. J. Foundations of Comput. Sci."},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: [27], vol.\u00a0I, pp. 41\u2013110","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"5_CR30","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":"5_CR31","first-page":"471","volume":"64","author":"S. Yu","year":"2005","unstructured":"Yu, S.: State complexity: Recent results and open problems. Fund. Inform.\u00a064, 471\u2013480 (2005)","journal-title":"Fund. Inform."}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00982-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T17:39:11Z","timestamp":1684949951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00982-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642009815","9783642009822"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00982-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}