{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:11:23Z","timestamp":1767852683931,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540734192","type":"print"},{"value":"9783540734208","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_77","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"901-912","source":"Crossref","is-referenced-by-count":17,"title":["A Combinatorial Theorem for Trees"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Colcombet","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"77_CR1","unstructured":"Blumensath, A.: Prefix-recognisable graphs and monadic second-order logic. Technical Report AIB-06-2001, RWTH Aachen (May 2001)"},{"key":"77_CR2","first-page":"285","volume-title":"IEEE Symposium on Logic In Computer Science","author":"M. Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Bounds in omega-regularity. In: IEEE Symposium on Logic In Computer Science, pp. 285\u2013296. IEEE Computer Society Press, Los Alamitos (2006)"},{"issue":"2","key":"77_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.2140\/pjm.1971.36.285","volume":"36","author":"T.C. Brown","year":"1971","unstructured":"Brown, T.C.: An interesting combinatorial method in the theory of locally finite semigroups. Pacific Journal of Mathematics\u00a036(2), 277\u2013294 (1971)","journal-title":"Pacific Journal of Mathematics"},{"key":"77_CR4","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":"77_CR5","first-page":"834","volume":"5","author":"J.R. B\u00fcchi","year":"1958","unstructured":"B\u00fcchi, J.R., Elgot, C.C.: Decision problems of weak second order arithmetics and finite automata. Notices of the American Math. Soc.\u00a05, 834 (1958)","journal-title":"Notices of the American Math. Soc."},{"key":"77_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.) FST TCS 2003. LNCS, vol.\u00a02914, pp. 112\u2013123. Springer, Heidelberg (2003)"},{"key":"77_CR7","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":"77_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)"},{"issue":"1\u20133","key":"77_CR9","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/S0304-3975(03)00344-X","volume":"310","author":"J. Chalopin","year":"2004","unstructured":"Chalopin, J., Leung, H.: On factorization forests of finite height. Theoretical Computer Science\u00a0310(1\u20133), 489\u2013499 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"77_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.2307\/1969317","volume":"54","author":"J.A. Green","year":"1951","unstructured":"Green, J.A.: On the structure of semigroups. Annals of Mathematics\u00a054(1), 163\u2013172 (1951)","journal-title":"Annals of Mathematics"},{"key":"77_CR11","unstructured":"Hashiguchi, K.: Relative star height, star height and finite automata with distance functions. In: Formal Properties of Finite Automata and Applications, pp. 74\u201388 (1988)"},{"issue":"39","key":"77_CR12","first-page":"455","volume":"3","author":"D. Kirsten","year":"2005","unstructured":"Kirsten, D.: Distance desert automata and the star height problem. RAIRO\u00a03(39), 455\u2013509 (2005)","journal-title":"RAIRO"},{"issue":"5","key":"77_CR13","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Information and Control\u00a09(5), 521\u2013530 (1966)","journal-title":"Information and Control"},{"key":"77_CR14","unstructured":"Niwinski, D., Walukiewicz, I.: Ambiguity problem for automata on infinite trees. Personal communication (1997)"},{"key":"77_CR15","first-page":"49","volume-title":"chapter Semigroups and automata on infinite words","author":"D. Perrin","year":"1995","unstructured":"Perrin, D., Pin, J-E.: Semigroups,Formal Languages and Groups. In: chapter Semigroups and automata on infinite words, pp. 49\u201372. Kluwer Academic Publishers, Dordrecht (1995)"},{"issue":"4","key":"77_CR16","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF02679467","volume":"30","author":"J.-E. Pin","year":"1997","unstructured":"Pin, J-E., Weil, P.: Polynomial closure and unambiguous product. Theory Comput. Syst.\u00a030(4), 383\u2013422 (1997)","journal-title":"Theory Comput. Syst."},{"key":"77_CR17","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. Trans. Amer. Math. soc.\u00a0141, 1\u201335 (1969)","journal-title":"Trans. Amer. Math. soc."},{"key":"77_CR18","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of omega-automata. In: FOCS, pp. 319\u2013327 (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"key":"77_CR19","doi-asserted-by":"publisher","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"Shelah, S.: The monadic theory of order. Annals Math.\u00a0102, 379\u2013419 (1975)","journal-title":"Annals Math."},{"issue":"1","key":"77_CR20","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0304-3975(90)90047-L","volume":"72","author":"I. Simon","year":"1990","unstructured":"Simon, I.: Factorization forests of finite height. Theor. Comput. Sci.\u00a072(1), 65\u201394 (1990)","journal-title":"Theor. Comput. Sci."},{"issue":"3-4","key":"77_CR21","first-page":"277","volume":"28","author":"I. Simon","year":"1994","unstructured":"Simon, I.: On semigroups of matrices over the tropical semiring. ITA\u00a028(3-4), 277\u2013294 (1994)","journal-title":"ITA"},{"key":"77_CR22","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0019-9958(81)90663-X","volume":"48","author":"W. Thomas","year":"1981","unstructured":"Thomas, W.: A combinatorial approach to the theory of \u03c9-automata. Information and Control\u00a048, 261\u2013283 (1981)","journal-title":"Information and Control"},{"key":"77_CR23","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Language Theory","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Language Theory, vol.\u00a0III, pp. 389\u2013455. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:11:29Z","timestamp":1619518289000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}