{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T12:43:45Z","timestamp":1648644225742},"reference-count":35,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1051\/ita\/2015002","type":"journal-article","created":{"date-parts":[[2015,4,27]],"date-time":"2015-04-27T06:33:06Z","timestamp":1430116386000},"page":"121-137","source":"Crossref","is-referenced-by-count":0,"title":["An upper bound on the complexity of recognizable tree languages"],"prefix":"10.1051","volume":"49","author":[{"given":"Olivier","family":"Finkel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Lecomte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Simonnet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2015,4,27]]},"reference":[{"key":"R1","unstructured":"A. Arnold, J. Duparc, F. Murlak and D. Niwinski, On the topological complexity of tree languages. In Logic and Automata: History and Perspectives, edited by J. Flum, E. Gr\u00e4del and T. Wilke. Amsterdam University Press (2007) 9\u201328."},{"key":"R2","unstructured":"Arnold A. and Niwinski D., Continuous separation of game languages.Fundamenta Informaticae81(2008) 19\u201328."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Bojanczyk and T. Place, Regular languages of infinite trees that are boolean combinations of open sets. InProc. of Automata, Languages, and Programming \u2013 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Part II. Edited by A. Czumaj, K. Mehlhorn, A.M. Pitts and R. Wattenhofer. Vol. 7392 ofLect. Notes Comput. Sci.Springer (2012) 104\u2013115.","DOI":"10.1007\/978-3-642-31585-5_13"},{"key":"R4","unstructured":"Bradfield J.C., Fixpoints, games and the difference hierarchy.RAIRO: ITA37(2003) 1\u201315."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J.C. Bradfield, J. Duparc and S. Quickert, Transfinite extension of the mu-calculus. InProc. of Computer Science Logic, 19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005. Edited by C.-H. Luke Ong. Vol. 3634 ofLect. Notes Comput. Sci.Springer (2005) 384\u2013396.","DOI":"10.1007\/11538363_27"},{"key":"R6","unstructured":"Cagnard B. and Simonnet P., Baire and automata.Discrete Math. Theor. Comput. Sci.9(2007) 255\u2013296."},{"key":"R7","unstructured":"Duparc J., Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank.J. Symbolic Logic66(2001) 56\u201386."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Facchini and H. Michalewski, Deciding the Borel complexity of regular tree languages. InProc. of Language, Life, Limits \u2013 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014.Edited by A. Beckmann, E. Csuhaj-Varj\u00fa and K. Meer. Vol. 8493 ofLect. Notes Comput. Sci.Springer (2014) 163\u2013172.","DOI":"10.1007\/978-3-319-08019-2_17"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Finkel O., The determinacy of context-free games.J. Symbolic Logic78(2013) 1115\u20131134.","DOI":"10.2178\/jsl.7804050"},{"key":"R10","unstructured":"O. Finkel, Infinite games specified by 2-tape automata (2013). Preprint, available from http:\/\/fr.arxiv.org\/abs\/1312.3797."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Finkel O. and Simonnet P., On recognizable tree languages beyond the Borel hierarchy.Fundamenta Informaticae95(2009) 287\u2013303.","DOI":"10.3233\/FI-2009-151"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"T. Gogacz, H. Michalewski, M. Mio and M. Skrzypczak, Measure properties of game tree languages. InProc. of Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014, Part I. Edited by E. Csuhaj-Varj\u00fa, M. Dietzfelbinger and Z. \u00c9sik. Vol. 8634 ofLect. Notes Comput. Sci.Springer (2014) 303\u2013314.","DOI":"10.1007\/978-3-662-44522-8_26"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Y. Gurevich and L. Harrington, Trees, automata, and games. InProc. of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. Edited by H.R. Lewis, B.B. Simons, W.A. Burkhard, and L.H. Landweber. ACM (1982) 60\u201365.","DOI":"10.1145\/800070.802177"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, W. Thomas and W. Wilke. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Vol. 2500 ofLect. Notes Comput. Sci.Springer (2002).","DOI":"10.1007\/3-540-36387-4"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"G. Hjorth, B. Khoussainov, A. Montalb\u00e1n and A. Nies, From automatic structures to Borel structures. InProc. of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24-27 June 2008, Pittsburgh, PA, USA. IEEE Computer Society (2008) 431\u2013441.","DOI":"10.1109\/LICS.2008.28"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Hummel, Unambiguous tree languages are topologically harder than deterministic ones. InProc. of Third International Symposium on Games, Automata Logics and Formal Verification, GandALF 2012, Napoli, Italy, September 6-8, 2012. Edited by M. Faella and A. Murano, Vol. 96 ofEPTCS(2012) 247\u2013260.","DOI":"10.4204\/EPTCS.96.19"},{"key":"R17","unstructured":"T. Jech, Set theory, 3rd edition. Springer (2002)."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Kanamori, The Higher Infinite. Springer-Verlag (1997).","DOI":"10.1007\/978-3-662-13167-1"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A.S. Kechris, Classical descriptive set theory. Springer-Verlag, New York (1995).","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Louveau and J. Saint-Raymond, The strength of Borel Wadge determinacy. InCabal Seminar 81\u201385. Vol. 1333 ofLect. Note Math.Springer (1988) 1\u201330.","DOI":"10.1007\/BFb0084967"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"H. Lescow and W. Thomas, Logical specifications of infinite computations. In A Decade of Concurrency. Edited by J.W. de Bakker, W.P. de Roever and Grzegorz Rozenberg. Vol. 803 ofLect. Notes Comput. Sci.Springer (1994) 583\u2013621.","DOI":"10.1007\/3-540-58043-3_29"},{"key":"R22","unstructured":"H. Michalewski and D. Niwinski, On topological completeness of regular tree languages. In Logic and Program Semantics \u2013 Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday. Edited by R.L. Constable and A. Silva. Vol. 7230 ofLect. Notes Comput. Sci.Springer (2012) 165\u2013179."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Y.N. Moschovakis, Descriptive set theory, vol. 155 ofMath. Surveys Monographs. American Mathematical Society, Providence, RI, 2nd edition (2009).","DOI":"10.1090\/surv\/155"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Murlak F., The Wadge hierarchy of deterministic tree languages.Log. Methods Comput. Sci.4(2008) 15.","DOI":"10.2168\/LMCS-4(4:15)2008"},{"key":"R25","unstructured":"D. Niwinski, An example of non Borel set of infinite trees recognizable by a Rabin automaton (1985). In Polish, manuscript."},{"key":"R26","unstructured":"Niwinski D. and Walukiewicz I., A gap property of deterministic tree languages.Theor. Comput. Sci.1(2003) 215\u2013231."},{"key":"R27","unstructured":"D. Perrin and J.-E. Pin, Infinite words, automata, semigroups, logic and games, vol. 141 ofPure Appl. Math.Elsevier (2004)."},{"key":"R28","unstructured":"Rabin M.O., Decidability of second-order theories and automata on infinite trees.Trans. Am. Math. Soc.141(1969) 1\u201335."},{"key":"R29","unstructured":"P. Simonnet,Automates et th\u00e9orie descriptive. Ph.D. thesis, Universit\u00e9 Paris VII (1992)."},{"key":"R30","unstructured":"Skurczynski J., The Borel hierarchy is infinite in the class of regular sets of trees.Theor. Comput. Sci.112(1993) 413\u2013418."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Saint Raymond J., Quasi-bounded trees and analytic inductions.Fundamenta Mathematicae191(2006) 175\u2013185.","DOI":"10.4064\/fm191-2-4"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"L. Staiger,\u03c9-languages. In vol. 3 ofHandb. Formal Languages. Springer, Berlin (1997) 339\u2013387.","DOI":"10.1007\/978-3-642-59126-6_6"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"W. Thomas, Automata on infinite objects. Formal models and semantics. Edited by J. van Leeuwen, vol. B.Handb. Theoret. Comput. Sci.Elsevier (1990) 135\u2013191.","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"W. Thomas, Languages, automata, and logic. In vol. 3 ofHandb. Formal Languages. Springer, Berlin (1997) 389\u2013455.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"R35","unstructured":"W. Wadge,Reducibility and determinateness in the Baire space. Ph.D. thesis, University of California, Berkeley (1983)."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015002\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T10:43:57Z","timestamp":1598957037000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":35,"journal-issue":{"issue":"2"},"alternative-id":["ita140040"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2015002","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}