The Use of complexity hierarchies in descriptive set theory and automata theory

• Autorzy: Andretta A. , Camerlo R.
• Języki publikacji: EN

Abstrakty

EN

The concept of a reduction between subsets of a given space is described, giving rise to various complexity hierarchies, studied both in descriptive set theory and in automata theory. We discuss in particular the Wadge and Lipschitz hierarchies for subsets of the Baire and Cantor spaces and the hierarchy of Borel reducibility for finitary relations on standard Borel spaces. The notions of Wadge and Lipschitz reductions are related to corresponding perfect information games.

Słowa kluczowe

EN

hierarchies; infinite games; Borel reducibility; automata theory

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2005
• Tom: Vol. 9, No 3
• Strony: 337--356
• Opis fizyczny: Bibliogr. 30 poz.

Twórcy

autor

Andretta A.

• Dipartimento di Matematica, Universit`a degli Studi di Torino, Via Carlo Alberto 10, 10123 Torino, Italy

autor

Camerlo R.

• Dipartimento di Matematica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy

Bibliografia

• [1] Wadge W W 1983 Reducibility and Determinateness on the Baire Space, PhD Thesis, University of California, Berkeley
• [2] Van Wesep R 1978 Wadge Degrees and Descriptive Set Theory, (Kechris A S and Moschovakis Y N, Eds.), Cabal Seminar 76-77, Springer, pp. 151–170
• [3] Louveau A 1983 Some Results in the Wadge Hierarchy of Borel Sets, (Kechris A S, Martin D A and Moschovakis Y N, Eds.), Cabal Seminar 79-81, Springer, pp. 28–55
• [4] Gale D and Stewart F M 1953 Ann. Math. Studies 28 245
• [5] Martin D A 1975 Ann. Math. 102 363
• [6] Harrington L A 1978 J. Symb. Logic 43 685
• [7] Andretta A 2003 Ann. Pure and Appl. Logic 123 163
• [8] Andretta A 2004 Ann. Pure and Appl. Logic (to appear)
• [9] Kechris A S 1995 Classical Descriptive Set Theory, Springer
• [10] Andretta A and Martin D A 2003 Fundamenta Mathematicae 177 175
• [11] Ornstein D S 1970 Adv. in Math. 4 337
• [12] Gromov M 1999 Metric Structures for Riemannian and Non-Riemannian Spaces, Birkh¨auser
• [13] Gao S and Kechris A S 2003 On the Classification of Polish Metric Spaces up to Isometry, AMS
• [14] Feldman J and Moore C C 1977 Trans. AMS 234 289
• [15] Harrington L A, Kechris A S and Louveau A 1990 J. AMS 3 903
• [16] Dougherty R, Jackson S and Kechris A S 1994 Trans. AMS 341 193
• [17] Andretta A, Camerlo R and Hjorth G 2001 Fundamenta Mathematicae 167 189
• [18] Camerlo R 2002 J. Symb. Logic 67 879
• [19] Adams S and Kechris A S 2000 J. AMS 13 909
• [20] Louveau A and Rosendal C 2005 Trans. AMS 357 4839
• [21] Marcone A and Rosendal C 2004 J. Symb. Logic 69 663
• [22] Camerlo R, http://calvino.polito.it/∼camerlo preprint
• [23] Camerlo R 2004 Fundamenta Mathematicae (to appear)
• [24] Wagner K 1979 Information and Control 43 123
• [25] Duparc J 2003 Theor. Comp. Sci. 290 1253
• [26] Finkel O 2001 Theor. Comp. Sci. 262 669
• [27] Finkel O 2001 Theor. Comp. Sci. 269 283
• [28] Duparc J, Finkel O and Ressayre J-P 2001 Theor. Comp. Sci. 257 85
• [29] B¨uchi J R 1960 Proc. Int. Congress on Logic, Mathematics and Philosophy of Science, Stanford University Press, pp. 1–11
• [30] Thomas W 1990 Automata on Infinte Objects, in: Handbook of Theoretical Computer Science, Vol. B (van Leeuwen J, Ed.), Elsevier, pp. 133–191