{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:12:15Z","timestamp":1725516735955},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705826"},{"type":"electronic","value":"9783540705833"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_33","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"398-409","source":"Crossref","is-referenced-by-count":22,"title":["The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Colcombet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christof","family":"L\u00f6ding","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4\/5","key":"33_CR1","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1051\/ita:1999121","volume":"33","author":"A. Arnold","year":"1999","unstructured":"Arnold, A.: The \u03bc-calculus alternation-depth hierarchy is strict on binary trees. Informatique Th\u00e9orique et Applications\u00a033(4\/5), 329\u2013340 (1999)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"33_CR2","unstructured":"Arnold, A., Duparc, J., Murlak, F., Niwi\u0144ski, D.: On the topological complexity of tree languages. In: Flum, J., Gr\u00e4del, E., Wilke, T. (eds.) Logic and automata: History and Perspectives, pp. 9\u201328. Amsterdam University Press (2007)"},{"key":"33_CR3","first-page":"285","volume-title":"Proceedings of LICS 2006","author":"M. Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Bounds in \u03c9-regularity. In: Proceedings of LICS 2006, pp. 285\u2013296. IEEE Computer Society Press, Los Alamitos (2006)"},{"issue":"2","key":"33_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0304-3975(97)00217-X","volume":"195","author":"J.C. Bradfield","year":"1998","unstructured":"Bradfield, J.C.: The modal \u03bc-calculus alternation hierarchy is strict. Theor. Comput. Sci.\u00a0195(2), 133\u2013153 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-540-74915-8_15","volume-title":"Computer Science Logic","author":"A. Carayol","year":"2007","unstructured":"Carayol, A., L\u00f6ding, C.: MSO on the infinite binary tree: Choice and order. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 161\u2013176. Springer, Heidelberg (2007)"},{"issue":"2","key":"33_CR6","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/0890-5401(88)90033-8","volume":"78","author":"K. Hashiguchi","year":"1988","unstructured":"Hashiguchi, K.: Algorithms for determining relative star height and star height. Inf. Comput.\u00a078(2), 124\u2013169 (1988)","journal-title":"Inf. Comput."},{"issue":"39","key":"33_CR7","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1051\/ita:2005027","volume":"3","author":"D. Kirsten","year":"2005","unstructured":"Kirsten, D.: Distance desert automata and the star height problem. RAIRO \u2013 Theoretical Informatics and Applications\u00a03(39), 455\u2013509 (2005)","journal-title":"RAIRO \u2013 Theoretical Informatics and Applications"},{"issue":"2\u20133","key":"33_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0168-0072(94)90086-8","volume":"69","author":"N. Klarlund","year":"1994","unstructured":"Klarlund, N.: Progress measures, immediate determinacy, and a subset construction for tree automata. Annals of Pure and Applied Logic\u00a069(2\u20133), 243\u2013268 (1994)","journal-title":"Annals of Pure and Applied Logic"},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/3-540-61440-0_119","volume-title":"Automata, Languages and Programming","author":"G. Lenzi","year":"1996","unstructured":"Lenzi, G.: A hierarchy theorem for the \u03bc-calculus. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 87\u201397. Springer, Heidelberg (1996)"},{"key":"33_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-16066-3_15","volume-title":"Computation Theory","author":"A.W. Mostowski","year":"1985","unstructured":"Mostowski, A.W.: Regular expressions for infinite trees and a standard form of automata. In: Skowron, A. (ed.) SCT 1984. LNCS, vol.\u00a0208, pp. 157\u2013168. Springer, Heidelberg (1985)"},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/3-540-16761-7_96","volume-title":"Automata, Languages and Programming","author":"D. Niwi\u0144ski","year":"1986","unstructured":"Niwi\u0144ski, D.: On fixed-point clones. In: Kott, L. (ed.) ICALP 1986. LNCS, vol.\u00a0226, pp. 464\u2013473. Springer, Heidelberg (1986)"},{"key":"33_CR12","unstructured":"Niwi\u0144ski, D., Walukiewicz, I.: Ambiguity problem for automata on infinite trees (unpublished note)"},{"key":"33_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/BFb0028571","volume-title":"STACS 98","author":"D. Niwi\u0144ski","year":"1998","unstructured":"Niwi\u0144ski, D., Walukiewicz, I.: Relating hierarchies of word and tree automata. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 320\u2013331. Springer, Heidelberg (1998)"},{"key":"33_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.entcs.2004.05.015","volume":"123","author":"D. Niwi\u0144ski","year":"2005","unstructured":"Niwi\u0144ski, D., Walukiewicz, I.: Deciding nondeterministic hierarchy of deterministic tree automata. Electr. Notes Theor. Comput. Sci.\u00a0123, 195\u2013208 (2005)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"33_CR15","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":"33_CR16","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: Handbook of Formal Language Theory, vol.\u00a0III, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"key":"33_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/3-540-45022-X_56","volume-title":"Automata, Languages and Programming","author":"T.F. Urba\u0144ski","year":"2000","unstructured":"Urba\u0144ski, T.F.: On deciding if deterministic Rabin language is in B\u00fcchi class. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 663\u2013674. Springer, Heidelberg (2000)"},{"issue":"9","key":"33_CR18","first-page":"473","volume":"13","author":"K.W. Wagner","year":"1977","unstructured":"Wagner, K.W.: Eine topologische Charakterisierung einiger Klassen regul\u00e4rer Folgenmengen. J. Inf. Process. Cybern. EIK\u00a013(9), 473\u2013487 (1977)","journal-title":"J. Inf. Process. Cybern. EIK"},{"issue":"1\u20132","key":"33_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(98)00009-7","volume":"200","author":"W. Zielonka","year":"1998","unstructured":"Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science\u00a0200(1\u20132), 135\u2013183 (1998)","journal-title":"Theoretical Computer Science"}],"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-70583-3_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:23:34Z","timestamp":1620001414000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}