{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T01:17:28Z","timestamp":1648862248809},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,2,6]],"date-time":"2014-02-06T00:00:00Z","timestamp":1391644800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,11]]},"DOI":"10.1007\/s00224-014-9533-0","type":"journal-article","created":{"date-parts":[[2014,2,5]],"date-time":"2014-02-05T00:32:48Z","timestamp":1391560368000},"page":"771-832","source":"Crossref","is-referenced-by-count":1,"title":["On First-Order Logic and CPDA Graphs"],"prefix":"10.1007","volume":"55","author":[{"given":"Christopher H.","family":"Broadbent","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,2,6]]},"reference":[{"key":"9533_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/978-3-540-31982-5_31","volume-title":"Foundations of Software Science and Computational Structures, Proceedings of the 8th International Conference, FOSSACS 2005, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005","author":"K. Aehlig","year":"2005","unstructured":"Aehlig, K., de Miranda, J.G., Ong, C.H.L.: Safety is not a restriction at level 2 for string languages. In: Sassone, V. (ed.) Foundations of Software Science and Computational Structures, Proceedings of the 8th International Conference, FOSSACS 2005, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005, Edinburgh, UK, 4\u20138 April 2005. Lecture Notes in Computer Science, vol. 3441, pp. 490\u2013504. Springer, Berlin (2005)"},{"key":"9533_CR2","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/B978-044482830-9\/50022-9","volume-title":"Handbook of Process Algebra","author":"J.C. Bradfield","year":"2001","unstructured":"Bradfield, J.C., Stirling, C.P.: Modal logics and mu-calculi: an introduction. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, pp. 293\u2013330. Elsevier, Amsterdam (2001)"},{"key":"9533_CR3","unstructured":"Broadbent, C.H.: On collapsible pushdown automata, their graphs and the power of links. Ph.D. thesis, The University of Oxford, Department of Computer Science (2011)"},{"key":"9533_CR4","series-title":"LIPIcs","first-page":"589","volume-title":"29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th","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.) 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th, Paris, France, 29 February\u20133 March 2012. LIPIcs, vol. 14, pp. 589\u2013600. Schloss Dagstuhl\/Leibniz-Zentrum fuer Informatik, Berlin (2012)"},{"key":"9533_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-3-642-31585-5_17","volume-title":"Automata, Languages, and Programming. Proceedings of the 39th International Colloquium, ICALP 2012, Part II","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.M., Wattenhofer, R. (eds.) Automata, Languages, and Programming. Proceedings of the 39th International Colloquium, ICALP 2012, Part II, Warwick, UK, 9\u201313 July 2012. Lecture Notes in Computer Science, vol. 7392, pp. 153\u2013164. Springer, Berlin (2012)"},{"key":"9533_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-642-31585-5_18","volume-title":"Automata, Languages, and Programming. Proceedings of the 39th International Colloquium, ICALP 2012, Part II","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.M., Wattenhofer, R. (eds.) Automata, Languages, and Programming. Proceedings of the 39th International Colloquium, ICALP 2012, Part II, Warwick, UK, 9\u201313 July 2012. Lecture Notes in Computer Science, vol. 7392, pp. 165\u2013176. Springer, Berlin (2012)"},{"key":"9533_CR7","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1109\/LICS.2010.40","volume-title":"Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010","author":"C.H. Broadbent","year":"2010","unstructured":"Broadbent, C.H., Carayol, A., Ong, C.H.L., Serre, O.: Recursion schemes and logical reflection. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, Edinburgh, UK 11\u201314 July 2010, pp. 120\u2013129. IEEE Computer Society, Los Alamitos (2010)"},{"key":"9533_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/3-540-45061-0_45","volume-title":"Automata, Languages and Programming, Proceedings of the 30th International Colloquium, ICALP 2003","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.) Automata, Languages and Programming, Proceedings of the 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands 30 June\u20134 July 2003. Lecture Notes in Computer Science, vol. 2719, pp. 556\u2013569. Springer, Berlin (2003)"},{"key":"9533_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/11549345_16","volume-title":"Mathematical Foundations of Computer Science, Proceedings of the 30th International Symposium, MFCS 2005","author":"A. Carayol","year":"2005","unstructured":"Carayol, A.: Regular sets of higher-order pushdown stacks. In: Jedrzejowicz, J., Szepietowski, A. (eds.) Mathematical Foundations of Computer Science, Proceedings of the 30th International Symposium, MFCS 2005, Gdansk, Poland, 29 August\u20132 September 2005. Lecture Notes in Computer Science, vol. 3618, pp. 168\u2013179. Springer, Berlin (2005)"},{"key":"9533_CR10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/LICS.2012.73","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012","author":"A. Carayol","year":"2012","unstructured":"Carayol, A., Serre, O.: Collapsible pushdown automata and labeled recursion schemes: equivalence, safety and effective selection. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, 25\u201328 June 2012, pp. 165\u2013174 (2012)"},{"key":"9533_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-540-24597-1_10","volume-title":"FSTTCS 2003: Foundations of Software Technology and Theoretical Computer Science, Proceedings of the 23rd Conference","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: Foundations of Software Technology and Theoretical Computer Science, Proceedings of the 23rd Conference, Mumbai, India, 15\u201317 December 2003. Lecture Notes in Computer Science, vol. 2914, pp. 112\u2013123. Springer, Berlin (2003)"},{"issue":"1","key":"9533_CR12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0304-3975(01)00089-5","volume":"290","author":"D. Caucal","year":"2003","unstructured":"Caucal, D.: On infinite transition graphs having a decidable monadic theory. Theor. Comput. Sci. 290(1), 79\u2013115 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9533_CR13","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1109\/LICS.2008.34","volume-title":"Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008","author":"M. Hague","year":"2008","unstructured":"Hague, M., Murawski, A.S., Ong, C.H.L., Serre, O.: Collapsible pushdown automata and recursion schemes. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, Pittsburgh, PA, USA, 24\u201327 June 2008, pp. 452\u2013461. IEEE Computer Society, Los Alamitos (2008)"},{"key":"9533_CR14","doi-asserted-by":"crossref","unstructured":"Kartzow, A.: Collapsible pushdown graphs of level 2 are tree-automatic. Log. Methods Comput. Sci. 9(1) (2013)","DOI":"10.2168\/LMCS-9(1:12)2013"},{"key":"9533_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1007\/978-3-642-32589-2_50","volume-title":"Mathematical Foundations of Computer Science 2012, Proceedings of the 37th International Symposium, MFCS 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.) Mathematical Foundations of Computer Science 2012, Proceedings of the 37th International Symposium, MFCS 2012, Bratislava, Slovakia, 27\u201331 August 2012. Lecture Notes in Computer Science, vol. 7464, pp. 566\u2013577. Springer, Berlin (2012)"},{"key":"9533_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/3-540-45931-6_15","volume-title":"Foundations of Software Science and Computation Structures, Proceedings of the 5th International Conference, FOSSACS 2002. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002","author":"T. Knapik","year":"2002","unstructured":"Knapik, T., Niwinski, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) Foundations of Software Science and Computation Structures, Proceedings of the 5th International Conference, FOSSACS 2002. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002, Grenoble, France, 8\u201312 April 2002. Lecture Notes in Computer Science, vol. 2303, pp. 205\u2013222. Springer, Berlin (2002)"},{"key":"9533_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1450","DOI":"10.1007\/11523468_117","volume-title":"Automata, Languages and Programming, Proceedings of the 32nd International Colloquium, ICALP 2005","author":"T. Knapik","year":"2005","unstructured":"Knapik, T., Niwinski, D., Urzyczyn, P., Walukiewicz, I.: Unsafe grammars and panic automata. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) Automata, Languages and Programming, Proceedings of the 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, 11\u201315 July 2005. Lecture Notes in Computer Science, vol. 3580, pp. 1450\u20131461. Springer, Berlin (2005)"},{"key":"9533_CR18","first-page":"416","volume-title":"Proceedings of the 36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2009","author":"N. Kobayashi","year":"2009","unstructured":"Kobayashi, N.: Types and higher-order recursion schemes for verification of higher-order programs. In: Shao, Z., Pierce, B.C. (eds.) Proceedings of the 36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2009, Savannah, GA, USA, 21\u201323 January 2009, pp.\u00a0416\u2013428. ACM, New York (2009)"},{"key":"9533_CR19","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"Kozen, D.: Results on the propositional mu-calculus. Theor. Comput. Sci. 27, 333\u2013354 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"9533_CR20","first-page":"587","volume-title":"Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011","author":"C.H.L. Ong","year":"2011","unstructured":"Ong, C.H.L., Ramsay, S.J.: Verifying higher-order functional programs with pattern-matching algebraic data types. In: Ball, T., Sagiv, M. (eds.) Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, 26\u201328 January 2011. pp. 587\u2013598. ACM, New York (2011)"},{"key":"9533_CR21","series-title":"LIPIcs","first-page":"603","volume-title":"28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011","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.) 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, Dortmund, Germany, 10\u201312 March 2011. LIPIcs, vol. 9, pp. 603\u2013614. Schloss Dagstuhl\/Leibniz-Zentrum fuer Informatik, Berlin (2011)"},{"key":"9533_CR22","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1109\/LICS.2012.62","volume-title":"Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012","author":"P. Parys","year":"2012","unstructured":"Parys, P.: On the significance of the collapse operation. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, 25\u201328 June 2012, pp.\u00a0521\u2013530. IEEE, New York (2012)"},{"issue":"2","key":"9533_CR23","first-page":"255","volume":"12","author":"E.L. Post","year":"1946","unstructured":"Post, E.L.: A variant of a recursively unsolvable problem. J. Symb. Log. 12(2), 255\u2013256 (1946)","journal-title":"J. Symb. Log."},{"issue":"70","key":"9533_CR24","first-page":"569","volume":"70","author":"B. Trachtenbrot","year":"1950","unstructured":"Trachtenbrot, B.: Impossibility of an algorithm for the decision problem on finite classes. Dokl. Akad. Nauk SSSR 70(70), 569\u2013572 (1950)","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9533-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9533-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9533-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T09:36:56Z","timestamp":1565170616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9533-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,6]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["9533"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9533-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,6]]}}}