Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (iterated differences of open sets). A similar characterization holds for Wadge one-to-one and finite-to-one completeness. We consider the same questions for the effectivization of the Wadge relation. We also show that for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff difference hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain. Copyright © Cambridge University Press 2014.

Registro:

Documento: Artículo
Título:Wadge hardness in Scott spaces and its effectivization
Autor:Becher, V.; Grigorieff, S.
Filiación:FCEyN, Universidad de Buenos Aires, CONICET, Argentina
LIAFA, CNRS, Université Paris Diderot - Paris 7, France
Laboratoire International Associé INFINIS, Universidad de Buenos Aires, Université Paris Diderot-Paris 7, France
Palabras clave:Hardness; Topology; Continuous domain; Difference hierarchies; Hausdorff; Natural number; One chain; Scott topology; Chains
Año:2015
Volumen:25
Número:7
Página de inicio:1520
Página de fin:1545
DOI: http://dx.doi.org/10.1017/S0960129513000248
Título revista:Mathematical Structures in Computer Science
Título revista abreviado:Math. Struct. Comput. Sci.
ISSN:09601295
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09601295_v25_n7_p1520_Becher

Referencias:

  • Abramsky, S., Jung, A., Domain theory (1994) Handbook of Logic in Computer Science, 3. , Gabbay, A and Maibaum (eds.) Oxford University Press
  • Becher, V., Grigorieff, S., Recursion and topology on 2≤ω for possibly infinite computations (2004) Theoretical Computer Science, 322 (1), pp. 85-136
  • Becher, V., Grigorieff, S., Random reals and possibly infinite computations. Part I: Randomness in ∅′ (2005) Journal of Symbolic Logic, 70 (3), pp. 891-913
  • Becher, V., Grigorieff, S., From index sets to randomness in ∅n. Random reals and possibly infinite computations, part II (2009) Journal of Symbolic Logic, 74 (1), pp. 124-156
  • Becher, V., Grigorieff, S., Borel and Hausdorff Hierarchies in Topological Spaces of Choquet Games and Their Effectivization, , This volume
  • Brattka, V., Hertling, P., Continuity and computability of relations (1994) Informatif Berichte, , Fern Universität Gesamthochschule in Hagen, Fachbereich Informatik
  • De Brecht, M., (2011) Quasi-Polish Spaces, 40p. , ArXiv:1108.1445v1
  • Edalat, A., Domains for computation in mathematics, physics and exact real aritmetic (1997) Bulletin of Symbolic Logic, 3 (4), pp. 401-452
  • Ershov, Y., On a hierarchy of sets II (1968) Algebra and Logic, 7 (4), pp. 15-47
  • Fokina, E.B., Friedman, S.-D., Tornquist, A., The effective theory of Borel equivalence relations (2010) Annals of Pure and Applied Logic, 161 (7), pp. 837-850
  • Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M., Scott, D.S., (2003) Continuous Lattices and Domains, , Cambridge University Press
  • Hertling, P., (1996) Unstetigkeitgrade von Funktionen in der Effektiven Analysis, , Ph.D. thesis, Fern Universität Gesamthochschule in Hagen
  • Hertling, P., Topological complexity with continuous operations (1996) Journal of Complexity, 12 (4), pp. 315-338
  • Ikegami, D., (2010) Games in Set Theory and Logic, , Ph.D. thesis, University of Amsterdam
  • Ikegami, D., Schlicht, P., Tanaka, H., (2012) Continuous Reducibility for the Real Line, , http://www.math.uni-bonn.de/people/schlicht/Ikegami%20Schlicht%20Tanaka%202012%20linespread.pdf, preprint, available at
  • Kechris, A.S., Classical Descriptive Set Theory (1995) Graduate Texts in Mathematics, , Springer
  • Kuratowski, K., (1966) Topology, 1. , Academic Press
  • Marker, D., (2002) Lecture Notes on Descriptive Set Theory, , http://homepages.math.uic.edu/~marker/math512/dst.ps, On Marker's home page
  • Moschovakis, Y., (1979) Descriptive Set Theory, 155. , American Mathematical Society
  • Rogers, H., (1967) Theory of Recursive Functions and Effective Computability, , McGraw-Hill
  • Schlicht, P., (2012) Continuous Reducibility and Dimension, , http://www.math.uni-bonn.de/people/schlicht/Continuous%20reducibility%20and%20dimension/crd.pdf, available at
  • Selivanov, V.L., Wadge degrees of ω-languages of deterministic Turing machines (2003) Theoretical Informatics and Applications, 37 (1), pp. 67-83
  • Selivanov, V.L., Extended abstract in STACS 2003 Proceedings (2003) Lecture Notes in Computer Science, 2607, pp. 97-108
  • Selivanov, V.L., Variations on Wadge reducibility (2005) Siberian Advances in Mathematics, 15 (3), pp. 44-80. , Also in Sixth Int. Workshop on Computability and Complexity in Analysis, Informatik Berichte, Uni-Hagen, 320-8/2004, 145-156
  • Selivanov, V.L., Variations on Wadge reducibility (2005) Electronic Notes in Theoretical Computer Science, 120, pp. 159-171. , Proceedings of the 6th Workshop on Computability and Complexity in Analysis (CCA 2004)
  • Selivanov, V.L., Hierarchies in φ-spaces and applications (2005) Mathematical Logic Quarterly, 51 (1), pp. 45-61
  • Selivanov, V.L., Towards a descriptive set theory for domain-like structures (2006) Theoretical Computer Science, 365 (3), pp. 258-282
  • Selivanov, V.L., Hierarchies of Δ<inf>2</inf>0-measurable k-partitions (2007) Mathematical Logic Quarterly, 53 (4-5), pp. 446-461
  • Selivanov, V.L., On the difference hierarchy in countably based T<inf>0</inf>-spaces (2008) Electronic Notes in Theoretical Computer Science, 221, pp. 257-269
  • Tang, A., Chain properties in Pω (1979) Theoretical Computer Science, 9 (2), pp. 153-172
  • Tang, A., Wadge reducibility and hausdorff difference hierarchy in Pω (1981) Lectures Notes in Mathematics, 871, pp. 360-371
  • Wadge, W.W., Degrees of complexity of subsets of the Baire space (1972) Notices of the American Mathematical Society, pp. A-714
  • Weihrauch, K., (2000) Computable Analysis. An Introduction, , Springer

Citas:

---------- APA ----------
Becher, V. & Grigorieff, S. (2015) . Wadge hardness in Scott spaces and its effectivization. Mathematical Structures in Computer Science, 25(7), 1520-1545.
http://dx.doi.org/10.1017/S0960129513000248
---------- CHICAGO ----------
Becher, V., Grigorieff, S. "Wadge hardness in Scott spaces and its effectivization" . Mathematical Structures in Computer Science 25, no. 7 (2015) : 1520-1545.
http://dx.doi.org/10.1017/S0960129513000248
---------- MLA ----------
Becher, V., Grigorieff, S. "Wadge hardness in Scott spaces and its effectivization" . Mathematical Structures in Computer Science, vol. 25, no. 7, 2015, pp. 1520-1545.
http://dx.doi.org/10.1017/S0960129513000248
---------- VANCOUVER ----------
Becher, V., Grigorieff, S. Wadge hardness in Scott spaces and its effectivization. Math. Struct. Comput. Sci. 2015;25(7):1520-1545.
http://dx.doi.org/10.1017/S0960129513000248