{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:04:29Z","timestamp":1740096269122,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642212536"},{"type":"electronic","value":"9783642212543"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-21254-3_33","type":"book-chapter","created":{"date-parts":[[2011,5,27]],"date-time":"2011-05-27T05:38:04Z","timestamp":1306474684000},"page":"414-426","source":"Crossref","is-referenced-by-count":4,"title":["Descriptional Complexity of Unambiguous Nested Word Automata"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","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":"33_CR2","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":"33_CR3","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: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 1\u201313. Springer, Heidelberg (2006)"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. Assoc. Comput. Mach. 56(3) (2009); full version of [3]","DOI":"10.1145\/1516512.1516518"},{"key":"33_CR5","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":"33_CR6","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":"33_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-12689-9_92","volume-title":"Foundations of Computation Theory","author":"B. Braunmuhl von","year":"1983","unstructured":"von Braunmuhl, B., Verbeek, R.: nput-driven languages are recognized in logn space. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 40\u201351. Springer, Heidelberg (1983)"},{"key":"33_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":"33_CR9","unstructured":"Comon, H., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007), Electronic book available from: tata.gforge.inria.fr"},{"key":"33_CR10","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":"33_CR11","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."},{"issue":"8","key":"33_CR12","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.ic.2007.01.008","volume":"205","author":"V. Geffert","year":"2007","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Inform. Comput.\u00a0205(8), 1173\u20131187 (2007), http:\/\/dx.doi.org\/10.1016\/j.ic.2007.01.008","journal-title":"Inform. Comput."},{"key":"33_CR13","doi-asserted-by":"publisher","first-page":"2961","DOI":"10.1016\/j.tcs.2009.01.004","volume":"410","author":"Y.-S. Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K.: Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci.\u00a0410, 2961\u20132971 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR14","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":"33_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-70844-5_1","volume-title":"Implementation and Applications of Automata","author":"M. Holzer","year":"2008","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic Finite Automata\u2014Recent Results on the Descriptional and Computational Complexity. In: Ibarra, O.H., Ravikumar, B. (eds.) CIAA 2008. LNCS, vol.\u00a05148, pp. 1\u201316. Springer, Heidelberg (2008)"},{"key":"33_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-00982-2_3","volume-title":"Language and Automata Theory and Applications","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 23\u201342. Springer, Heidelberg (2009)"},{"key":"33_CR17","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":"33_CR18","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."},{"issue":"4","key":"33_CR19","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539793252092","volume":"27","author":"H. Leung","year":"1998","unstructured":"Leung, H.: Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM J. Comput.\u00a027(4), 1073\u20131082 (1998)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"33_CR20","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(5), 975\u2013984 (2005), http:\/\/dx.doi.org\/10.1142\/S0129054105003418","journal-title":"Internat. J. Foundations Comput. Sci."},{"key":"33_CR21","doi-asserted-by":"publisher","first-page":"1178","DOI":"10.1016\/j.ic.2008.03.018","volume":"206","author":"G. Liu","year":"2008","unstructured":"Liu, G., Martin-Vide, C., Salomaa, A., Yu, S.: The state-complexity of two combined operations: Star of catenation and star of reversal. Inform. Comput.\u00a0206, 1178\u20131186 (2008)","journal-title":"Inform. Comput."},{"key":"33_CR22","doi-asserted-by":"crossref","unstructured":"Madhusudan, P., Parlato, G.: The tree width of auxiliary storage. In: Proc. 38th ACM Symposium on Principles of Programming Languages, POPL 2011, pp. 283\u2013294 (2011)","DOI":"10.1145\/1926385.1926419"},{"key":"33_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","author":"K. Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 422\u2013435. Springer, Heidelberg (1980), http:\/\/dx.doi.org\/10.1007\/3-540-10003-2_89"},{"key":"33_CR24","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., Sarukkai, S. (eds.) FST TCS 1998. LNCS, vol.\u00a01530, pp. 134\u2013146. Springer, Heidelberg (1998)"},{"key":"33_CR25","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), http:\/\/dx.doi.org\/10.1007\/978-3-642-15155-2_49"},{"key":"33_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-642-18381-2_36","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"A. Okhotin","year":"2011","unstructured":"Okhotin, A.: Comparing linear conjunctive languages to subfamilies of the context-free languages. In: \u010cern\u00e1, I., Gyim\u00f3thy, T., Hromkovi\u010d, J., Jefferey, K., Kr\u00e1lovi\u0107, R., Vukoli\u0107, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol.\u00a06543, pp. 431\u2013443. Springer, Heidelberg (2011)"},{"key":"33_CR27","doi-asserted-by":"crossref","unstructured":"Okhotin, A., Salomaa, K.: State complexity of operations on input-driven pushdown automata (February 2011) (manuscript in preparation)","DOI":"10.1007\/978-3-642-22993-0_44"},{"key":"33_CR28","doi-asserted-by":"publisher","first-page":"3290","DOI":"10.1016\/j.tcs.2009.05.002","volume":"410","author":"X. Piao","year":"2009","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoret. Comput. Sci.\u00a0410, 3290\u20133302 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"33_CR29","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 type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput.\u00a018(6), 1263\u20131282 (1989), http:\/\/dx.doi.org\/10.1137\/0218083","journal-title":"SIAM J. Comput."},{"volume-title":"Handbook of Formal Languages","year":"1997","key":"33_CR30","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol.\u00a0I-III. Springer, Heidelberg (1997)"},{"key":"33_CR31","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1016\/j.ic.2010.11.021","volume":"209","author":"K. Salomaa","year":"2011","unstructured":"Salomaa, K.: Limitations of lower bound methods for deterministic nested word automata. Inform. Comput.\u00a0209, 580\u2013589 (2011)","journal-title":"Inform. Comput."},{"key":"33_CR32","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":"33_CR33","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":"33_CR34","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: [30], vol.\u00a0I, pp. 41\u2013110","DOI":"10.1007\/978-3-642-59136-5_2"}],"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-21254-3_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T03:11:32Z","timestamp":1560222692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21254-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642212536","9783642212543"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21254-3_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}