{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:47:09Z","timestamp":1794383229728,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540255932","type":"print"},{"value":"9783540320142","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11417170_5","type":"book-chapter","created":{"date-parts":[[2010,12,16]],"date-time":"2010-12-16T14:29:35Z","timestamp":1292509775000},"page":"39-54","source":"Crossref","is-referenced-by-count":27,"title":["The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Aehlig","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jolie G.","family":"de Miranda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. -H. Luke","family":"Ong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","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\u2013504. Springer, Heidelberg (2005) (To appear)","DOI":"10.1007\/978-3-540-31982-5_31"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Asperti, A., Danos, V., Laneve, C., Regnier, L.: Paths in the lambda-calculus. In: Proceedings of the Ninth Annual IEEE Symposium an Logic in Computer Science (LICS 1994), July 1994, pp. 426\u2013436 (1994)","DOI":"10.1109\/LICS.1994.316048"},{"key":"5_CR3","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)"},{"issue":"1","key":"5_CR4","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 Comput. Sci.\u00a0151(1), 125\u2013162 (1995)","journal-title":"Theoretical Comput. Sci."},{"issue":"1","key":"5_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0304-3975(96)00171-5","volume":"175","author":"J.R. Kennaway","year":"1997","unstructured":"Kennaway, J.R., Klop, J.W., Sleep, M.R., de Vries, F.J.: Infinitary lambda calculus. Theoretical Comput. Sci.\u00a0175(1), 93\u2013125 (1997)","journal-title":"Theoretical Comput. Sci."},{"key":"5_CR6","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":"5_CR7","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":"5_CR8","doi-asserted-by":"crossref","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P., Walukiewicz, I.: Unsafe grammars, panic automata, and decidability. In: Manuscript (October 2004)","DOI":"10.1007\/11523468_117"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","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, pp. 36\u201352. Springer, Heidelberg (2000)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(87)90133-2","volume":"54","author":"D.E. Muller","year":"1987","unstructured":"Muller, D.E., Schupp, P.E.: Alternating automata on infinite trees. Theoretical Comput. Sci.\u00a054, 267\u2013276 (1987)","journal-title":"Theoretical Comput. Sci."},{"key":"5_CR11","first-page":"1","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":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/BFb0055090","volume-title":"Automata, Languages and Programming","author":"M.Y. Vardi","year":"1998","unstructured":"Vardi, M.Y.: Reasoning about the past with two-way automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 628\u2013641. Springer, Heidelberg (1998)"},{"issue":"2","key":"5_CR13","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"Walukiewicz, I.: Pushdown processes: Games and model-checking. Information and Computation\u00a0164(2), 234\u2013263 (2001)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Typed Lambda Calculi and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11417170_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:24:10Z","timestamp":1559867050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11417170_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540255932","9783540320142"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11417170_5","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b135690","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}