{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:30:52Z","timestamp":1780381852844,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540206804","type":"print"},{"value":"9783540245971","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24597-1_10","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T07:39:20Z","timestamp":1280389160000},"page":"112-123","source":"Crossref","is-referenced-by-count":46,"title":["The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Arnaud","family":"Carayol","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"W\u00f6hrle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"Blumensath, A.: Prefix-recognisable graphs and monadic second-order logic. Technical Report AIB-2001-06, RWTH Aachen (2001)"},{"key":"10_CR2","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":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/3-540-45061-0_48","volume-title":"Automata, Languages and Programming","author":"A. Carayol","year":"2003","unstructured":"Carayol, A., Colcombet, T.: On equivalent representations of infinite structures. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 599\u2013610. Springer, Heidelberg (2003)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Carayol, A., W\u00f6hrle, S.: The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. Technical report, RWTH Aachen (2003)","DOI":"10.1007\/978-3-540-24597-1_10"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/3-540-44612-5_23","volume-title":"Mathematical Foundations of Computer Science 2000","author":"O. Carton","year":"2000","unstructured":"Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 275\u2013284. Springer, Heidelberg (2000)"},{"key":"10_CR6","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":"10_CR7","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":"10_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: Monadic second-order definable graph transductions: A survey. Theoretical Computer Science\u00a0126, 53\u201375 (1994)","journal-title":"Theoretical Computer Science"},{"key":"10_CR9","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, graph coverings and unfoldings of transition systems. Annals of Pure and Applied Logic\u00a092, 35\u201362 (1998)","journal-title":"Annals of Pure and Applied Logic"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/3-540-09526-8_23","volume-title":"Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science","author":"W. Damm","year":"1979","unstructured":"Damm, W.: An algebraic extension of the Chomsky-hierarchy. In: Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science. LNCS, vol.\u00a074, pp. 266\u2013276. Springer, Heidelberg (1979)"},{"key":"10_CR11","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 hierarchies. Theoretical Computer Science\u00a020, 95\u2013208 (1982)","journal-title":"Theoretical Computer Science"},{"key":"10_CR12","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":"10_CR13","volume-title":"Finite Model Theory","author":"H.D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0890-5401(91)90015-T","volume":"95","author":"J. Engelfriet","year":"1991","unstructured":"Engelfriet, J.: Iterated stack automata and complexity classes. Information and Computation\u00a095, 21\u201375 (1991)","journal-title":"Information and Computation"},{"key":"10_CR15","series-title":"T. Knapik, D. Niwi\u0144ski, and P. Urzyczyn","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 pusdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. T. Knapik, D. Niwi\u0144ski, and P. Urzyczyn, vol.\u00a02303, pp. 205\u2013222. Springer, Heidelberg (2002)"},{"key":"10_CR16","unstructured":"Stirling, C.: Decidability of bisimulation equivalence for pushdown processes (submitted)"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-540-45138-9_6","volume-title":"Mathematical Foundations of Computer Science 2003","author":"W. Thomas","year":"2003","unstructured":"Thomas, W.: Constructing infinite graphs with a decidable MSO-theory. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 113\u2013124. Springer, Heidelberg (2003)"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0304-3975(01)00185-2","volume":"275","author":"I. Walukiewicz","year":"2002","unstructured":"Walukiewicz, I.: Monadic second-order logic on tree-like structures. Theoretical Computer Science\u00a0275, 311\u2013346 (2002)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24597-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T23:42:41Z","timestamp":1559346161000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24597-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206804","9783540245971"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24597-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}