{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:18Z","timestamp":1725488958458},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74456-6_4","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"15-21","source":"Crossref","is-referenced-by-count":2,"title":["Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes"],"prefix":"10.1007","author":[{"given":"C. -H. L.","family":"Ong","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1145\/322063.322074","volume":"25","author":"N.D. Jones","year":"1978","unstructured":"Jones, N.D., Muchnick, S.S.: Complexity of finite memory programs with recursion. Journal of the Association for Computing Machinery\u00a025, 312\u2013321 (1978)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D.E. Muller","year":"1985","unstructured":"Muller, D.E., Schupp, P.E.: The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science\u00a037, 51\u201375 (1985)","journal-title":"Theoretical Computer Science"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/10722167_7","volume-title":"Computer Aided Verification","author":"O. Kupferman","year":"2000","unstructured":"Kupferman, O., Vardi, M.Y.: An automata-theoretic approach to reasoning about infinite-state systems. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol.\u00a01855, Springer, Heidelberg (2000)"},{"key":"4_CR4","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 mathematics Doklady\u00a015, 1170\u20131174 (1974)","journal-title":"Soviet mathematics Doklady"},{"key":"4_CR5","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":"4_CR6","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A. Aho","year":"1968","unstructured":"Aho, A.: Indexed grammars - an extension of context-free grammars. J. ACM\u00a015, 647\u2013671 (1968)","journal-title":"J. ACM"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","volume":"20","author":"W. Damm","year":"1982","unstructured":"Damm, W.: The IO- and OI-hierarchy. Theoretical Computer Science\u00a020, 95\u2013207 (1982)","journal-title":"Theoretical Computer Science"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(86)80016-X","volume":"71","author":"W. Damm","year":"1986","unstructured":"Damm, W., Goerdt, A.: An automata-theoretical characterization of the OI-hierarchy. Information and Control\u00a071, 1\u201332 (1986)","journal-title":"Information and Control"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/3-540-45413-6_21","volume-title":"Typed Lambda Calculi and Applications","author":"T. Knapik","year":"2001","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P.: Deciding monadic theories of hyperalgebraic trees. In: Abramsky, S. (ed.) TLCA 2001. LNCS, vol.\u00a02044, pp. 253\u2013267. Springer, Heidelberg (2001)"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society\u00a0141, 1\u201335 (1969)","journal-title":"Transactions of the American Mathematical Society"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(95)00049-3","volume":"151","author":"B. Courcelle","year":"1995","unstructured":"Courcelle, B.: The monadic second-order logic of graphs IX: machines and their behaviours. Theoretical Computer Science\u00a0151, 125\u2013162 (1995)","journal-title":"Theoretical Computer Science"},{"key":"4_CR12","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.) ETAPS 2002 and FOSSACS 2002. LNCS, vol.\u00a02303, pp. 205\u2013222. Springer, Heidelberg (2002)"},{"key":"4_CR13","unstructured":"de Miranda, J.: Structures generated by higher-order grammars and the safety constraint. PhD thesis, University of Oxford (2006)"},{"key":"4_CR14","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":"4_CR15","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":"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.) FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science. LNCS, vol.\u00a02914, pp. 112\u2013123. Springer, Heidelberg (2003)"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/3-540-61440-0_128","volume-title":"Automata, Languages and Programming","author":"D. Caucal","year":"1996","unstructured":"Caucal, D.: On infinite transition graphs having a decidable monadic theory. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 194\u2013205. Springer, Heidelberg (1996)"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1006\/inco.2000.2917","volume":"163","author":"J.M.E. Hyland","year":"2000","unstructured":"Hyland, J.M.E., Ong, C.H.L.: On Full Abstraction for PCF: I. Models, observables and the full abstraction problem, II. Dialogue games and innocent strategies, III. A fully abstract and universal game model. Information and Computation\u00a0163, 285\u2013408 (2000)","journal-title":"Information and Computation"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/LICS.2006.38","volume-title":"Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006)","author":"C.H.L. Ong","year":"2006","unstructured":"Ong, C.H.L.: On model-checking trees generated by higher-order recursion schemes. In: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 81\u201390. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"4_CR19","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","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":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/11417170_5","volume-title":"Typed Lambda Calculi and Applications","author":"K. Aehlig","year":"2005","unstructured":"Aehlig, K., Miranda, J.G.d., Ong, C.H.L.: The monadic second order theory of trees given by arbitrary level two recursion schemes is decidable. In: Urzyczyn, P. (ed.) TLCA 2005. LNCS, vol.\u00a03461, pp. 39\u201354. Springer, Heidelberg (2005)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/11874683_7","volume-title":"Computer Science Logic","author":"K. Aehlig","year":"2006","unstructured":"Aehlig, K.: A finite semantics for simply-typed lambda terms for infinite runs of automata. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 104\u2013118. Springer, Heidelberg (2006)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Hague, M., Murawski, A.S., Ong, C.H.L., Serre, O.: Collapsible pushdown automata and recursion schemes. Technical report, Oxford University Computing Laboratory, p. 56 (Preprint, 2007), downloable from users.comlab.ox.ac.uk\/luke.ong\/publications\/cpda-long.pdf","DOI":"10.1109\/LICS.2008.34"},{"key":"4_CR23","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","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.) FOSSACS 2005. LNCS, vol.\u00a03441, pp. 490\u2013501. Springer, Heidelberg (2005)"},{"key":"4_CR24","unstructured":"Blum, W.: A tool for constructing structures generated by higher-order recursion schemes and collapsible pushdown automata (2007), web.comlab.ox.ac.uk\/oucl\/work\/william.blum\/"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"157","author":"I. Walukiewicz","year":"2001","unstructured":"Walukiewicz, I.: Pushdown processes: games and model-checking. Information and Computation\u00a0157, 234\u2013263 (2001)","journal-title":"Information and Computation"},{"key":"4_CR26","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":"4_CR27","first-page":"255","volume":"XV","author":"M. Nivat","year":"1975","unstructured":"Nivat, M.: On the interpretation of recursive polyadic program schemes. Symp. Math.\u00a0XV, 255\u2013281 (1975)","journal-title":"Symp. Math."},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1007\/11523468_74","volume-title":"Automata, Languages and Programming","author":"A.S. Murawski","year":"2005","unstructured":"Murawski, A.S., Ong, C.H.L., Walukiewicz, I.: Idealized Algol with ground recursion and DPDA equivalence. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 917\u2013929. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T18:11:11Z","timestamp":1629569471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540744559","9783540744566"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}