{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:39Z","timestamp":1725663279069},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_40","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:01:49Z","timestamp":1330203709000},"page":"416-423","source":"Crossref","is-referenced-by-count":0,"title":["The Borel hierarchy is infinite in the class of regular sets of trees"],"prefix":"10.1007","author":[{"given":"Jerzy","family":"Skurczy\u0144ski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","first-page":"166","DOI":"10.2307\/2271090","volume":"34","author":"J. R. B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H., Definability in the monadic second-order theory of successor, Journal of Symbolic Logic 34 (1969), pp.166\u2013170.","journal-title":"Journal of Symbolic Logic"},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/cm-15-2-271-274","volume":"XV","author":"R. Engelking","year":"1966","unstructured":"Engelking, R., Holszty\u0144ski, W., Sikorski, R., Some examples of Borel sets, Colloquium Mathematicum vol.XV fasc.2 (1966), pp.271\u2013274.","journal-title":"Colloquium Mathematicum"},{"key":"40_CR3","unstructured":"Kuratowski, K., Topology vol. I and II (the translation of the French edition), Academic Press and Polish Scientific Publishers (1966)."},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0304-3975(87)90085-5","volume":"52","author":"T. Moriya","year":"1987","unstructured":"Moriya, T., Topological characterizations of infinite tree languages, Theoretical Computer Science 52 (1987), pp. 165\u2013171.","journal-title":"Theoretical Computer Science"},{"key":"40_CR5","unstructured":"Mostowski, A.W., Finite automata on infinite trees and subtheories of SkS, Les Arbres en Algebre et en Programmation, 5-eme Colloque de Lille (1980), pp.228\u2013240."},{"key":"40_CR6","first-page":"55","volume":"411","author":"A. W. Mostowski","year":"1980","unstructured":"Mostowski, A.W., Types of finite automata acceptances and subtheories of SkS, 3rd Symposium on Math. Found. of Comp. Sci., ICS PAS Reports 411 (1980), pp.55\u201358.","journal-title":"3rd Symposium on Math. Found. of Comp. Sci."},{"key":"40_CR7","first-page":"509","volume":"23","author":"A. W. Mostowski","year":"1987","unstructured":"Mostowski, A.W., Hierarchies of weak monadic formulas for two successors arithmetic, J. Inf. Process. Cybern. EIK 23 (1987), pp.509\u2013515.","journal-title":"J. Inf. Process. Cybern. EIK"},{"key":"40_CR8","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/3-540-16761-7_77","volume":"226","author":"D. E. Muller","year":"1986","unstructured":"Muller, D.E., Saoudi, A., Schupp, P., Alternating automata, the weak monadic theory of the tree and its complexity, Proc. 13th ICALP (L.Kott ed), Lect.Notes in Comp. Sci.226 (1986), pp.275\u2013283.","journal-title":"Lect.Notes in Comp. Sci."},{"key":"40_CR9","unstructured":"Mostowski, A.W., Skurczy\u0144ski, J., Wagner, K., Deterministic automata on infinite trees and the Borel hierarchy, Proc. Fourth Hung. Comp. Sci. Conf. (1985), M.Arat\u00f3, I.K\u00e0tai, L.Varga eds., pp.103\u2013115."},{"key":"40_CR10","unstructured":"Niwi\u0144ski, D., The example of non-Borel set of infinite trees recognizable by a Rabin automaton (in Polish), manuscript, Univ.of Warsaw (1985), 9 pages."},{"key":"40_CR11","first-page":"1","volume":"141","author":"M. O. Rabin","year":"1969","unstructured":"Rabin, M.O., Decidability of second-order theories and automata on infinite trees, Trans. of Amer. Math. Soc. 141 (1969), pp.1\u201335.","journal-title":"Trans. of Amer. Math. Soc."},{"key":"40_CR12","unstructured":"Rabin, M.O., Weakly definable relations and special automata, Math.Logic and Found. of Set Theory (1970), pp.1\u201323."},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Rabin, M.O., Automata on infinite objects and Church's problem, Regional Conference Series in Mathematics 13 (1972), Amer. Math. Soc., Providence,, Rhode Island.","DOI":"10.1090\/cbms\/013"},{"key":"40_CR14","unstructured":"Skurczy\u0144ski, J., Automata on infinite trees with conditions for sets of accessible states, unpublished manuscript, Univ. of Gda\u0144sk (1986), 10 pages."},{"key":"40_CR15","unstructured":"Thomas, W., Automata on infinite objects, in: Handbook of Theoretical Computer Science, North-Holland, to appear."},{"key":"40_CR16","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0019-9958(79)90653-3","volume":"43","author":"K. Wagner","year":"1979","unstructured":"Wagner, K., On \u03c9-regular sets, Information and Control 43 (1979), pp.123\u2013177.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:03:40Z","timestamp":1619571820000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}