{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:11Z","timestamp":1759639091556},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319096971"},{"type":"electronic","value":"9783319096988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09698-8_9","type":"book-chapter","created":{"date-parts":[[2014,8,18]],"date-time":"2014-08-18T00:52:51Z","timestamp":1408323171000},"page":"84-102","source":"Crossref","is-referenced-by-count":4,"title":["Input-Driven Pushdown Automata with Limited Nondeterminism"],"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":[{"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-16, pp. 202\u2013211 (2004)","key":"9_CR1","DOI":"10.1145\/1007352.1007390"},{"doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. Journal of the ACM\u00a056(3) (2009)","key":"9_CR2","DOI":"10.1145\/1516512.1516518"},{"key":"9_CR3","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 of NFA minimization. J. Comput. System Sci.\u00a078, 198\u2013210 (2012)","journal-title":"J. Comput. System Sci."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-0208(08)73072-X","volume":"102","author":"B. Braunm\u00fchl von","year":"1985","unstructured":"von Braunm\u00fchl, B., Verbeek, R.: Input driven languages are recognized in logn space. North-Holland Mathematics Studies\u00a0102, 1\u201319 (1985)","journal-title":"North-Holland Mathematics Studies"},{"key":"9_CR5","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":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-642-39274-0_10","volume-title":"Implementation and Application of Automata CIAA 2013","author":"D. Chistikov","year":"2013","unstructured":"Chistikov, D., Majumdar, R.: A uniformization theorem for nested word to word transductions. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol.\u00a07982, pp. 97\u2013108. Springer, Heidelberg (2013)"},{"key":"9_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":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/978-3-642-39274-0_26","volume-title":"Implementation and Application of Automata, CIAA 2013","author":"D. Debarbieux","year":"2013","unstructured":"Debarbieux, D., Gauwin, O., Niehren, J., Sebastian, T., Zergaoui, M.: Early nested word automata for XPath query answering on XML streams. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol.\u00a07982, pp. 292\u2013305. Springer, Heidelberg (2013)"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0020-0190(88)90148-2","volume":"26","author":"P.W. Dymond","year":"1988","unstructured":"Dymond, P.W.: Input-driven languages are in logn depth. Information Processing Letters\u00a026, 247\u2013250 (1988)","journal-title":"Information Processing Letters"},{"key":"9_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. Information Processing Letters\u00a0109, 13\u201317 (2008)","journal-title":"Information Processing Letters"},{"key":"9_CR11","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. Journal of Universal Computer Science\u00a08, 193\u2013234 (2002)","journal-title":"Journal of Universal Computer Science"},{"issue":"2","key":"9_CR12","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. Information and Computation\u00a086(2), 179\u2013194 (1990)","journal-title":"Information and Computation"},{"key":"9_CR13","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":"9_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. Information and Computation\u00a0172, 202\u2013217 (2002)","journal-title":"Information and Computation"},{"issue":"7","key":"9_CR15","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/j.ipl.2010.12.013","volume":"111","author":"M. Lange","year":"2011","unstructured":"Lange, M.: P-hardness of the emptiness problem for visibly pushdown automata. Inf. Proc. Lett.\u00a0111(7), 338\u2013341 (2011)","journal-title":"Inf. Proc. Lett."},{"key":"9_CR16","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, 1073\u20131082 (1998)","journal-title":"SIAM J. Comput."},{"key":"9_CR17","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":"9_CR18","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., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 422\u2013435. Springer, Heidelberg (1980)"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ic.2012.01.003","volume":"212","author":"A. Okhotin","year":"2012","unstructured":"Okhotin, A.: Unambiguous finite automata over a unary alphabet. Inform. Comput.\u00a0212, 15\u201336 (2012)","journal-title":"Inform. Comput."},{"doi-asserted-by":"crossref","unstructured":"Okhotin, A., Piao, X., Salomaa, K.: Descriptional complexity of input-driven pushdown automata. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive 2012. LNCS, vol.\u00a07300, pp. 186\u2013206. Springer, Heidelberg (2012)","key":"9_CR20","DOI":"10.1007\/978-3-642-31644-9_13"},{"key":"9_CR21","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)"},{"unstructured":"Okhotin, A., Salomaa, K.: Complexity of input-driven pushdown automata. In: Hemaspaandra, L.A. (ed.) SIGACT News Complexity Theory Column 82. SIGACT News (to appear, 2014)","key":"9_CR22"},{"key":"9_CR23","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.\u00a07386, pp. 252\u2013265. Springer, Heidelberg (2012)"},{"key":"9_CR24","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, Languages and Combinatorics\u00a017, 245\u2013264 (2012)","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-39310-5_21","volume-title":"Descriptional Complexity of Formal Systems","author":"A. Palioudakis","year":"2013","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Comparisons between measures of nondeterminism on finite automata. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol.\u00a08031, pp. 217\u2013228. Springer, Heidelberg (2013)"},{"key":"9_CR26","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"},{"doi-asserted-by":"crossref","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2009)","key":"9_CR27","DOI":"10.1017\/CBO9780511808876"},{"doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0I, pp. 41\u2013110 (1997)","key":"9_CR28","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09698-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T16:21:49Z","timestamp":1558974109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09698-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319096971","9783319096988"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09698-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}