{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T05:14:37Z","timestamp":1740028477256,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_36","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"434-446","source":"Crossref","is-referenced-by-count":2,"title":["Decidability of MSO Theories of Tree Structures"],"prefix":"10.1007","author":[{"given":"Angelo","family":"Montanari","sequence":"first","affiliation":[]},{"given":"Gabriele","family":"Puppis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","unstructured":"Barthelmann, K.: On equational simple graphs. Technical Report\u00a09, Universit\u00e4t Mainz, Institut f\u00fcr Informatik (1997)"},{"key":"36_CR2","first-page":"1","volume-title":"Proceedings of the International Congress on Logic, Methodology and Philosophy of Science","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Proceedings of the International Congress on Logic, Methodology and Philosophy of Science, pp. 1\u201311. Stanford University Press, Stanford (1960)"},{"key":"36_CR3","unstructured":"Blumensath, A.: Prefix-recognizable graphs and monadic second-order logic. Technical Report AIB-06-2001, RWTH Aachen (2001)"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"Blumensath, A., Gradel, E.: Automatic structures. Logic in Computer Science, 51\u201362 (2000)","DOI":"10.1109\/LICS.2000.855755"},{"key":"36_CR5","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":"36_CR6","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":"36_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/inco.2001.3139","volume":"176","author":"O. Carton","year":"2002","unstructured":"Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Information and Computation\u00a0176, 51\u201365 (2002)","journal-title":"Information and Computation"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(92)90278-N","volume":"106","author":"D. Caucal","year":"1992","unstructured":"Caucal, D.: On the regular structure of prefix rewriting. Theoretical Computer Science\u00a0106, 61\u201386 (1992)","journal-title":"Theoretical Computer Science"},{"key":"36_CR9","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":"36_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0304-3975(01)00089-5","volume":"290","author":"D. Caucal","year":"2003","unstructured":"Caucal, D.: On infinite transition graphs having a decidable monadic theory. Theoretical Computer Science\u00a0290, 79\u2013115 (2003)","journal-title":"Theoretical Computer Science"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF02088013","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"Courcelle, B.: The monadic second-order logic of graphs II: Infinite graphs of bounded tree width. Mathematical Systems Theory\u00a021, 187\u2013221 (1989)","journal-title":"Mathematical Systems Theory"},{"key":"36_CR12","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"36_CR13","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 graph transductions: a survey. Theoretical Computer Science\u00a0126, 53\u201375 (1994)","journal-title":"Theoretical Computer Science"},{"key":"36_CR14","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"},{"issue":"2","key":"36_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2307\/2269808","volume":"31","author":"C.C. Elgot","year":"1966","unstructured":"Elgot, C.C., Rabin, M.O.: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. Journal of Symbolic Logic\u00a031(2), 169\u2013181 (1966)","journal-title":"Journal of Symbolic Logic"},{"issue":"4","key":"36_CR16","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1093\/logcom\/12.4.641","volume":"12","author":"A. Montanari","year":"2002","unstructured":"Montanari, A., Peron, A., Policriti, A.: Extending Kamp\u2019s theorem to model time granularity. Journal of Logic and Computation\u00a012(4), 641\u2013678 (2002)","journal-title":"Journal of Logic and Computation"},{"key":"36_CR17","doi-asserted-by":"crossref","unstructured":"Montanari, A., Puppis, G.: Decidability of MSO theories of tree structures. Research Report\u00a001, Dipartimento di Matematica e Informatica, Universita di Udine, Italy (2004)","DOI":"10.1007\/978-3-540-30538-5_36"},{"key":"36_CR18","doi-asserted-by":"crossref","unstructured":"Montanari, A., Puppis, G.: Decidability of the theory of the totally unbounded \u03c9-layered structure. In: Proceedings of the 11th International Symposium on Temporal Representation and Reasoning TIME, pp. 156\u2013160 (2004)","DOI":"10.1109\/TIME.2004.1314434"},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D. Muller","year":"1985","unstructured":"Muller, D., Schupp, P.: The theory of ends, pushdown automata, and second-order logics. Theoretical Computer Science\u00a037, 51\u201375 (1985)","journal-title":"Theoretical Computer Science"},{"key":"36_CR20","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":"36_CR21","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozemberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a03, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"key":"36_CR22","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":"36_CR23","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"},{"issue":"1","key":"36_CR24","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/inco.1998.2787","volume":"152","author":"G. Zhang","year":"1999","unstructured":"Zhang, G.: Automata, boolean matrices, and ultimate periodicity. Information and Computation\u00a0152(1), 138\u2013154 (1999)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T12:11:46Z","timestamp":1739967106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}