{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T04:02:04Z","timestamp":1743998524407,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_6","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"49-60","source":"Crossref","is-referenced-by-count":1,"title":["Simple Models for Recursive Schemes"],"prefix":"10.1007","author":[{"given":"Igor","family":"Walukiewicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"6_CR1","first-page":"1","volume":"3","author":"K. Aehlig","year":"2007","unstructured":"Aehlig, K.: A finite semantics of simply-typed lambda terms for infinite runs of automata. Logical Methods in Computer Science\u00a03(1), 1\u201323 (2007)","journal-title":"Logical Methods in Computer Science"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/11417170_5","volume-title":"Typed Lambda Calculi and Applications","author":"K. Aehlig","year":"2005","unstructured":"Aehlig, K., de Miranda, J.G., 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)"},{"issue":"4","key":"6_CR3","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A.V. Aho","year":"1968","unstructured":"Aho, A.V.: Indexed grammars \u2013 an extension of context-free grammars. J. ACM\u00a015(4), 647\u2013671 (1968)","journal-title":"J. ACM"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Barendregt, H.: The type free lambda calculus. In: Handbook of Mathematical Logic, ch. D.7, pp. 1091\u20131132. North-Holland (1977)","DOI":"10.1016\/S0049-237X(08)71129-7"},{"issue":"5","key":"6_CR5","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1016\/j.ic.2008.09.003","volume":"207","author":"H. Barendregt","year":"2009","unstructured":"Barendregt, H., Klop, J.W.: Applications of infinitary lambda calculus. Inf. Comput.\u00a0207(5), 559\u2013582 (2009)","journal-title":"Inf. Comput."},{"key":"6_CR6","unstructured":"Cachat, T., Walukiewicz, I.: The Complexity of Games on Higher Order Pushdown Automata. Internal report"},{"key":"6_CR7","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":"6_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":"6_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(78)90008-7","volume":"6","author":"B. Courcelle","year":"1978","unstructured":"Courcelle, B.: A representation of trees by languages I. Theor. Comput. Sci.\u00a06, 255\u2013279 (1978)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Recursive applicative program schemes. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 459\u2013492. Elesvier (1990)","DOI":"10.1016\/B978-0-444-88074-1.50014-7"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Nivat, M.: Algebraic families of interpretations. In: FOCS (1976)","DOI":"10.1109\/SFCS.1976.3"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0168-0072(97)00048-1","volume":"92","author":"B. Courcelle","year":"1998","unstructured":"Courcelle, B., Walukiewicz, I.: Monadic second-order logic, graphs and unfoldings of transition systems. Annals of Pure and Applied Logic\u00a092, 35\u201362 (1998)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"6_CR13","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\u2013 and OI\u2013hierarchies. Theoretical Computer Science\u00a020(2), 95\u2013208 (1982)","journal-title":"Theoretical Computer Science"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Dezani-Ciancaglini, M., Giovannetti, E., de\u2019 Liguoro, U.: Intersection Types, Lambda-models and B\u00f6hm Trees. In: MSJ-Memoir \u201cTheories of Types and Proofs\u201d, vol.\u00a02, pp. 45\u201397. Mathematical Society of Japan (1998)","DOI":"10.2969\/msjmemoirs\/00201C020"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Engelfriet, J.: Iterated push-down automata and complexity classes. In: 15th STOC 1983, pp. 365\u2013373 (1983)","DOI":"10.1145\/800061.808767"},{"issue":"3","key":"6_CR16","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/S0022-0000(77)80034-2","volume":"15","author":"J. Engelfriet","year":"1977","unstructured":"Engelfriet, J., Schmidt, E.: IO and OI. Journal of Computer and System Sciences\u00a015(3), 328\u2013353 (1977)","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Hague, M., Murawski, A.S., Ong, C.-H.L., Serre, O.: Collapsible pushdown automata and recursion schemes. In: LICS 2008, pp. 452\u2013461. IEEE Computer Society (2008)","DOI":"10.1109\/LICS.2008.34"},{"key":"6_CR18","first-page":"82","volume-title":"Problems of Cybernetics I","author":"Y. Ianov","year":"1969","unstructured":"Ianov, Y.: The logical schemes of algorithms. In: Problems of Cybernetics I, pp. 82\u2013140. Pergamon, Oxford (1969)"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/3-540-07854-1_198","volume-title":"Mathematical Foundations of Computer Science 1976","author":"K. Indermark","year":"1976","unstructured":"Indermark, K.: Schemes with Recursion on Higher Types. In: Mazurkiewicz, A. (ed.) MFCS 1976. LNCS, vol.\u00a045, pp. 352\u2013358. Springer, Heidelberg (1976)"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Jancar, P.: Decidability of DPDA language equivalence via first-order grammars. In: LICS 2012 (2012)","DOI":"10.1109\/LICS.2012.51"},{"key":"6_CR21","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":"6_CR22","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":"6_CR23","doi-asserted-by":"crossref","unstructured":"Kobayashi, N.: Types and higher-order recursion schemes for verification of higher-order programs. In: POPL 2009, pp. 416\u2013428. ACM (2009)","DOI":"10.1145\/1594834.1480933"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Kobayashi, N.: Higher-order model checking: From theory to practice. In: LICS 2011, pp. 219\u2013224 (2011)","DOI":"10.1109\/LICS.2011.15"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Kobayashi, N., Ong, C.-H.L.: Complexity of model checking recursion schemes for fragments of the modal mu-calculus. Logical Methods in Computer Science\u00a07(4) (2011)","DOI":"10.2168\/LMCS-7(4:9)2011"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Kobayashi, N., Ong, L.: A type system equivalent to modal mu-calculus model checking of recursion schemes. In: LICS 2009, pp. 179\u2013188 (2009)","DOI":"10.1109\/LICS.2009.29"},{"key":"6_CR27","unstructured":"Manna, Z.: Mathematical Theory of Computation. McGraw-Hill (1974)"},{"key":"6_CR28","first-page":"1170","volume":"15","author":"A. Maslov","year":"1974","unstructured":"Maslov, A.: The hierarchy of indexed languages of an arbitrary level. Soviet. Math. Doklady\u00a015, 1170\u20131174 (1974)","journal-title":"Soviet. Math. Doklady"},{"key":"6_CR29","first-page":"38","volume":"12","author":"A. Maslov","year":"1976","unstructured":"Maslov, A.: Multilevel stack automata. Problems of Information Transmission\u00a012, 38\u201343 (1976)","journal-title":"Problems of Information Transmission"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Milner, R.: Models of LCF. Memo AIM-186. Stanford University (1973)","DOI":"10.21236\/AD0758645"},{"key":"6_CR31","unstructured":"Nivat, M.: On interpretation of recursive program schemes. In: Symposia Mathematica, vol.\u00a015 (1975)"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Ong, C.-H.L.: On model-checking trees generated by higher-order recursion schemes. In: LICS 2006, pp. 81\u201390 (2006)","DOI":"10.1109\/LICS.2006.38"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Parys, P.: On the significance of the collapse operation. In: LICS 2012 (2012)","DOI":"10.1109\/LICS.2012.62"},{"issue":"3","key":"6_CR34","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(77)90044-5","volume":"5","author":"G.D. Plotkin","year":"1977","unstructured":"Plotkin, G.D.: LCF considered as a programming language. Theor. Comput. Sci.\u00a05(3), 223\u2013255 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-642-02261-6_5","volume-title":"Logic, Language, Information and Computation","author":"S. Salvati","year":"2009","unstructured":"Salvati, S.: Recognizability in the Simply Typed Lambda-Calculus. In: Ono, H., Kanazawa, M., de Queiroz, R. (eds.) WoLLIC 2009. LNCS, vol.\u00a05514, pp. 48\u201360. Springer, Heidelberg (2009)"},{"key":"6_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-31585-5_34","volume-title":"Automata, Languages, and Programming","author":"S. Salvati","year":"2012","unstructured":"Salvati, S., Manzonetto, G., Gehrke, M., Barendregt, H.: Loader and Urzyczyn Are Logically Related. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 364\u2013376. Springer, Heidelberg (2012)"},{"key":"6_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-22012-8_12","volume-title":"Automata, Languages and Programming","author":"S. Salvati","year":"2011","unstructured":"Salvati, S., Walukiewicz, I.: Krivine Machines and Higher-Order Schemes. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 162\u2013173. Springer, Heidelberg (2011)"},{"key":"6_CR38","unstructured":"Scott, D.: Continuous lattices. In: Proc. of Dalhousie Conference. Lecture Notes in Mathematics, vol.\u00a0188, pp. 311\u2013366. Springer (1972)"},{"issue":"1-2","key":"6_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G. S\u00e9nizergues","year":"2001","unstructured":"S\u00e9nizergues, G.: L(A)=L(B)? Decidability results from complete formal systems. Theor. Comput. Sci.\u00a0251(1-2), 1\u2013166 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"6_CR40","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/S0304-3975(02)00027-0","volume":"281","author":"G. S\u00e9nizergues","year":"2002","unstructured":"S\u00e9nizergues, G.: L(A)=L(B)? A simplified decidability proof. Theor. Comput. Sci.\u00a0281(1-2), 555\u2013608 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/3-540-45465-9_70","volume-title":"Automata, Languages and Programming","author":"C. Stirling","year":"2002","unstructured":"Stirling, C.: Deciding DPDA Equivalence Is Primitive Recursive. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 821\u2013832. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T11:22:24Z","timestamp":1743938544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}