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 and CONICET, Argentina
LIAFA, CNRS and Université Paris Diderot - Paris 7, France
Palabras clave:Hardness; Topology; Continuous domain; Difference hierarchies; Hausdorff; Natural number; One chain; Scott topology; Chains
Año:2014
Volumen:39
Número:11
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_v39_n11_p_Becher

Referencias:

  • Abramsky, S., Jung, A., (1994) Domain Theory, 3. , Gabbay, A and Maibaum eds Handbook of Logic in Computer Science 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 O (2005) Journal of Symbolic Logic, 70 (3), pp. 891-913
  • Becher, V., Grigorieff, S., From index sets to randomness in O 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., (1994) Continuity and Computability of Relations, , Informatif Berichte 164, Fern Universitat Gesamthochschule in Hagen, Fachbereich Informatik
  • De Brecht, M., (2011) Quasi-Polish Spaces, p. 40. , 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 Universitat 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, Preprint, , http://www.math.uni-bonn.de/people/schlicht/Ikegami%20Schlicht%20Tanaka%202012%20linespread.pdf
  • Kechris, A.S., Classical descriptive set theory (1995) Graduate Texts in Mathematics, , Springer
  • Kuratowski, K., (1966) Topology, 1. , Academic Press
  • Marker, D., Lecture notes on descriptive set theory (2002) On Markers Home Page, , http://homepages.math.uic.edu/marker/math512/dst.ps
  • 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
  • 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) Proceedings of the 6th Workshop on Computability and Complexity in Analysis (CCA 2004) Electronic Notes in Theoretical Computer Science, 120, pp. 159-171
  • 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 δ02 -measurable k-partitions (2007) Mathematical Logic Quarterly, 53 (4-5), pp. 446-461
  • Selivanov, V.L., On the difference hierarchy in countably based T0-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., (1972) Degrees of Complexity of Subsets of the Baire Space, , Notices of the American Mathematical Society A-714
  • Weihrauch, K., (2000) Computable Analysis, , An Introduction Springer

Citas:

---------- APA ----------
Becher, V. & Grigorieff, S. (2014) . Wadge hardness in Scott spaces and its effectivization. Mathematical Structures in Computer Science, 39(11).
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 39, no. 11 (2014).
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. 39, no. 11, 2014.
http://dx.doi.org/10.1017/S0960129513000248
---------- VANCOUVER ----------
Becher, V., Grigorieff, S. Wadge hardness in Scott spaces and its effectivization. Math. Struct. Comput. Sci. 2014;39(11).
http://dx.doi.org/10.1017/S0960129513000248