{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:20Z","timestamp":1780743680643,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540433668","type":"print"},{"value":"9783540459316","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45931-6_15","type":"book-chapter","created":{"date-parts":[[2007,6,9]],"date-time":"2007-06-09T04:53:52Z","timestamp":1181364832000},"page":"205-222","source":"Crossref","is-referenced-by-count":83,"title":["Higher-Order Pushdown Trees Are Easy"],"prefix":"10.1007","author":[{"given":"Teodor","family":"Knapik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damian","family":"Niwi\u0144ski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Urzyczyn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"15_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/3-540-61440-0_128","volume-title":"23th International Colloquium on Automata Languages and Programming","author":"D. Caucal","year":"1996","unstructured":"D. Caucal. On infinite transition graphs having a decidable monadic second-order theory. In F. Meyer auf der Heide and B. Monien, editors, 23th International Colloquium on Automata Languages and Programming, LNCS 1099, pages 194\u2013205, 1996. A long version will appear in TCS."},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(95)00049-3","volume":"151","author":"B. Courcelle","year":"1995","unstructured":"B. Courcelle. The monadic second-order theory of graphs IX: Machines and their behaviours. Theoretical Comput. Sci., 151:125\u2013162, 1995.","journal-title":"Theoretical Comput. Sci."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"B. Courcelle and T. Knapik. The evaluation of first-order substitution is monadic second-order compatible. Theoretical Comput. Sci., 2002. To appear.","DOI":"10.1016\/S0304-3975(02)00012-9"},{"issue":"2","key":"15_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","volume":"20","author":"W. Damm","year":"1982","unstructured":"W. Damm. The IO-and OI-hierarchies. Theoretical Comput. Sci., 20(2):95\u2013208, 1982.","journal-title":"Theoretical Comput. Sci."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(86)80016-X","volume":"71","author":"W. Damm","year":"1986","unstructured":"W. Damm and A. Goerdt. An automata-theoreticc haracterization of the OIhierarchy. Information and Control, 71:1\u201332, 1986.","journal-title":"Information and Control"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"J. Engelfriet. Iterated push-down automata and complexity classes. In Proc. 15th STOC, pages 365\u2013373, 1983.","DOI":"10.1145\/800061.808767"},{"key":"15_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-48340-3_14","volume-title":"Mathematical Foundations of Computer Science 1999","author":"H. Hungar","year":"1999","unstructured":"H. Hungar. Model checking and higher-order recursion. In L. Pacholski, M. Kuty\u0142owski and T. Wierzbicki, editors, Mathematical Foundations of Computer Science 1999, LNCS 1672, pages 149\u2013159, 1999."},{"key":"15_CR8","unstructured":"B. Jacobs and J. Rutten. A tutorial on (co)algebras and (co)induction. Bulletin of EATCS, 1997(62):222\u2013259."},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(92)90210-7","volume":"93","author":"A.J. Kfoury","year":"1992","unstructured":"A.J. Kfoury, J. Tiuryn and P. Urzyczyn. On the expressive power of finitely typed and universally polymorphic recursive procedures. Theoretical Comput. Sci., 93:1\u201341, 1992.","journal-title":"Theoretical Comput. Sci."},{"key":"15_CR10","unstructured":"A. Kfoury and P. Urzyczyn. Finitely typed functional programs, part II: comparisons to imperative languages. Report, Boston University, 1988."},{"key":"15_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/3-540-45413-6_21","volume-title":"Typed Lambda Calculi and Applications, 5th International Conference","author":"T. Knapik","year":"2001","unstructured":"T. Knapik, D. Niwi\u0144ski, and P. Urzyczyn. Deciding monadic theories of hyperalgebraictrees. In Typed Lambda Calculi and Applications, 5th International Conference, LNCS 2044, pages 253\u2013267. Springer-Verlag, 2001."},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"497","DOI":"10.3233\/FI-1989-12404","volume":"12","author":"W. Kowalczyk","year":"1989","unstructured":"W. Kowalczyk, D. Niwi\u0144ski, and J. Tiuryn. A generalization of of Cook\u2019s auxiliarypushdown-automata theorem. Fundamenta Informaticae, 12:497\u2013506, 1989.","journal-title":"Fundamenta Informaticae"},{"key":"15_CR13","series-title":"Lect Notes Comput Sci","volume-title":"Computer Aided Verification, Proc. 12th Int. Conference","author":"O. Kupferman","year":"2000","unstructured":"O. Kupferman and M. Vardi. An automata-theoreticapproach to reasoning about infinite-state systems. In Computer Aided Verification, Proc. 12th Int. Conference, Lecture Notes in Computer Science. Springer-Verlag, 2000."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D. Muller","year":"1985","unstructured":"D. Muller and P. Schupp. The theory of ends, pushdown automata, and secondorder logic. Theoretical Comput. Sci., 37:51\u201375, 1985.","journal-title":"Theoretical Comput. Sci."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M. O. Rabin","year":"1969","unstructured":"M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Soc, 141:1\u201335, 1969.","journal-title":"Trans. Amer. Soc"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pages 389\u2013455. Springer-Verlag, 1997.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"15_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BFb0016242","volume-title":"Proc. 12th MFCS","author":"J. Tiuryn","year":"1986","unstructured":"J. Tiuryn. Higher-order arrays and stacks in programming: An application of complexity theory to logics of programs. In Proc. 12th MFCS, LNCS 233, pages 177\u2013198. Springer-Verlag, 1986."},{"issue":"2","key":"15_CR18","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"I. Walukiewicz. Pushdown processes: Games and model checking. Information and Computation, 164(2):234\u2013263, 2001.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45931-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T21:40:15Z","timestamp":1628977215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45931-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433668","9783540459316"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45931-6_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}