{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:02Z","timestamp":1725600302110},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229923"},{"type":"electronic","value":"9783642229930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_44","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"485-496","source":"Crossref","is-referenced-by-count":4,"title":["State Complexity of Operations on Input-Driven Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"44_CR1","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)"},{"doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: ACM Symposium on Theory of Computing STOC 2004, Chicago, USA, June 13\u201316, pp. 202\u2013211 (2004)","key":"44_CR2","DOI":"10.1145\/1007352.1007390"},{"key":"44_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1516512.1516518","volume":"56","author":"R. Alur","year":"2009","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. Journal of the ACM\u00a056, 3 (2009)","journal-title":"Journal of the ACM"},{"key":"44_CR4","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. Theoretical Computer Science\u00a0119, 267\u2013291 (1993)","journal-title":"Theoretical Computer Science"},{"key":"44_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.: Input-driven languages are recognized in logn space. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 40\u201351. Springer, Heidelberg (1983)"},{"key":"44_CR6","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":"44_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-642-13089-2_18","volume-title":"Language and Automata Theory and Applications","author":"S. Crespi Reghizzi","year":"2010","unstructured":"Crespi Reghizzi, S., Mandrioli, D.: Operator precedence and the visibly pushdown property. In: Dediu, A.-H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. LNCS, vol.\u00a06031, pp. 214\u2013226. Springer, Heidelberg (2010)"},{"key":"44_CR8","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.tcs.2009.02.025","volume":"410","author":"M. Domaratzki","year":"2009","unstructured":"Domaratzki, M., Okhotin, A.: State complexity of power. Theoretical Computer Science\u00a0410, 24\u201325 (2009)","journal-title":"Theoretical Computer Science"},{"key":"44_CR9","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. Theoretical Computer Science\u00a0410, 2961\u20132971 (2009)","journal-title":"Theoretical Computer Science"},{"key":"44_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. International Journal of Foundations of Computer Science\u00a014, 1087\u20131102 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"E.L. Leiss","year":"1981","unstructured":"Leiss, E.L.: Succinct representation of regular languages by Boolean automata. Theoretical Computer Science\u00a013, 323\u2013330 (1981)","journal-title":"Theoretical Computer Science"},{"key":"44_CR12","first-page":"1373","volume":"11","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Mathematics Doklady\u00a011, 1373\u20131375 (1970)","journal-title":"Soviet Mathematics Doklady"},{"key":"44_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"44_CR14","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":"44_CR15","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":"44_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-642-21254-3_33","volume-title":"Language and Automata Theory and Applications","author":"A. Okhotin","year":"2011","unstructured":"Okhotin, A., Salomaa, K.: Descriptional Complexity of Unambiguous Nested Word Automata. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol.\u00a06638, pp. 414\u2013426. Springer, Heidelberg (2011)"},{"key":"44_CR17","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. Theoretical Computer Science\u00a0410, 3290\u20133302 (2009)","journal-title":"Theoretical Computer Science"},{"key":"44_CR18","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.ipl.2005.06.011","volume":"98","author":"N. Rampersad","year":"2006","unstructured":"Rampersad, N.: The state complexity of L 2 and L k . Information Processing Letters\u00a098, 231\u2013234 (2006)","journal-title":"Information Processing Letters"},{"key":"44_CR19","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. Information and Computation\u00a0209, 580\u2013589 (2011)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:10:17Z","timestamp":1606187417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}