{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:30:10Z","timestamp":1725795010914},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_23","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T01:30:40Z","timestamp":1401672640000},"page":"300-313","source":"Crossref","is-referenced-by-count":0,"title":["First-Order Logic on CPDA Graphs"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Parys","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","first-page":"1170","volume":"15","author":"A.N. Maslov","year":"1974","unstructured":"Maslov, A.N.: The hierarchy of indexed languages of an arbitrary level. Soviet Math. Dokl.\u00a015, 1170\u20131174 (1974)","journal-title":"Soviet Math. Dokl."},{"key":"23_CR2","first-page":"38","volume":"12","author":"A.N. Maslov","year":"1976","unstructured":"Maslov, A.N.: Multilevel stack automata. Problems of Information Transmission\u00a012, 38\u201343 (1976)","journal-title":"Problems of Information Transmission"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-45931-6_15","volume-title":"Foundations of Software Science and Computation Structures","author":"T. Knapik","year":"2002","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol.\u00a02303, pp. 205\u2013222. Springer, Heidelberg (2002)"},{"key":"23_CR4","series-title":"LIPIcs","first-page":"603","volume-title":"STACS","author":"P. Parys","year":"2011","unstructured":"Parys, P.: Collapse operation increases expressive power of deterministic higher order pushdown automata. In: Schwentick, T., D\u00fcrr, C. (eds.) STACS. LIPIcs, vol.\u00a09, pp. 603\u2013614. Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik (2011)"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Parys, P.: On the significance of the collapse operation. In: LICS, pp. 521\u2013530. IEEE (2012)","DOI":"10.1109\/LICS.2012.62"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Hague, M., Murawski, A.S., Ong, C.-H.L., Serre, O.: Collapsible pushdown automata and recursion schemes. In: LICS, pp. 452\u2013461. IEEE Computer Society (2008)","DOI":"10.1109\/LICS.2008.34"},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1450","DOI":"10.1007\/11523468_117","volume-title":"Automata, Languages and Programming","author":"T. Knapik","year":"2005","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P., Walukiewicz, I.: Unsafe grammars and panic automata. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1450\u20131461. Springer, Heidelberg (2005)"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/3-540-45687-2_13","volume-title":"Mathematical Foundations of Computer Science 2002","author":"D. Caucal","year":"2002","unstructured":"Caucal, D.: On infinite terms having a decidable monadic theory. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 165\u2013176. Springer, Heidelberg (2002)"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/3-540-45061-0_45","volume-title":"Automata, Languages and Programming","author":"T. Cachat","year":"2003","unstructured":"Cachat, T.: Higher order pushdown automata, the Caucal hierarchy of graphs and parity games. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 556\u2013569. Springer, Heidelberg (2003)"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-540-24597-1_10","volume-title":"FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science","author":"A. Carayol","year":"2003","unstructured":"Carayol, A., W\u00f6hrle, S.: The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol.\u00a02914, pp. 112\u2013123. Springer, Heidelberg (2003)"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Kartzow, A.: Collapsible pushdown graphs of level 2 are tree-automatic. Logical Methods in Computer Science\u00a09(1) (2013)","DOI":"10.2168\/LMCS-9(1:12)2013"},{"key":"23_CR12","unstructured":"Broadbent, C.H.: On collapsible pushdown automata, their graphs and the power of links. PhD thesis, University of Oxford (2011)"},{"key":"23_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-642-31585-5_17","volume-title":"Automata, Languages, and Programming","author":"C.H. Broadbent","year":"2012","unstructured":"Broadbent, C.H.: Prefix rewriting for nested-words and collapsible pushdown automata. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 153\u2013164. Springer, Heidelberg (2012)"},{"key":"23_CR14","series-title":"LIPIcs","first-page":"589","volume-title":"STACS","author":"C.H. Broadbent","year":"2012","unstructured":"Broadbent, C.H.: The limits of decidability for first order logic on CPDA graphs. In: D\u00fcrr, C., Wilke, T. (eds.) STACS. LIPIcs, vol.\u00a014, pp. 589\u2013600. Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik (2012)"},{"key":"23_CR15","unstructured":"Broadbent, C.H.: On first-order logic and CPDA graphs. Accepted to Theory of Computing Systems"},{"key":"23_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-642-31585-5_18","volume-title":"Automata, Languages, and Programming","author":"C.H. Broadbent","year":"2012","unstructured":"Broadbent, C.H., Carayol, A., Hague, M., Serre, O.: A saturation method for collapsible pushdown systems. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 165\u2013176. Springer, Heidelberg (2012)"},{"key":"23_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-642-32589-2_50","volume-title":"Mathematical Foundations of Computer Science 2012","author":"A. Kartzow","year":"2012","unstructured":"Kartzow, A., Parys, P.: Strictness of the collapsible pushdown hierarchy. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 566\u2013577. Springer, Heidelberg (2012)"},{"key":"23_CR18","first-page":"569","volume":"70","author":"B. Trachtenbrot","year":"1950","unstructured":"Trachtenbrot, B.: Impossibility of an algorithm for the decision problem in finite classes. Doklady Akad. Nauk.\u00a070, 569\u2013572 (1950)","journal-title":"Doklady Akad. Nauk."}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T19:37:14Z","timestamp":1558899434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}