Document Open Access Logo

Descriptive Complexity on Non-Polish Spaces II

Author Mathieu Hoyrup

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.132.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Mathieu Hoyrup
  • Université de Lorraine, CNRS, Inria, LORIA, Nancy, France

Acknowledgements

I want to thank the anonymous referees for their useful comments, and for suggesting the generalization of Corollary 2.4 to quasi-zero-dimensional spaces.

Cite As Get BibTex

Mathieu Hoyrup. Descriptive Complexity on Non-Polish Spaces II. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 132:1-132:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.132

Abstract

This article is a study of descriptive complexity of subsets of represented spaces. Two competing measures of descriptive complexity are available. The first one is topological and measures how complex it is to obtain a set from open sets using boolean operations. The second one measures how complex it is to test membership in the set, and we call it symbolic complexity because it measures the complexity of the symbolic representation of the set. While topological and symbolic complexity are equivalent on countably-based spaces, they differ on more general spaces. Our investigation is aimed at explaining this difference and highly suggests that it is related to the well-known mismatch between topological and sequential aspects of topological spaces.

Subject Classification

ACM Subject Classification
  • Theory of computation → Turing machines
  • Mathematics of computing → Point-set topology
Keywords
  • Represented space
  • Computable analysis
  • Descriptive set theory
  • Scott topology

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Antonin Callard and Mathieu Hoyrup. Descriptive complexity on non-polish spaces. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 8:1-8:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.8.
  2. Matthew de Brecht. Quasi-Polish spaces. Ann. Pure Appl. Logic, 164(3):356-381, 2013. URL: https://doi.org/10.1016/j.apal.2012.11.001.
  3. Matthew de Brecht, Arno Pauly, and Matthias Schröder. Overt choice. Computability, ?, 2019. URL: https://doi.org/10.3233/COM-190253.
  4. Matthew de Brecht, Matthias Schröder, and Victor Selivanov. Base-complexity classifications of qcb₀-spaces. Computability, 5(1):75-102, 2016. URL: https://doi.org/10.3233/COM-150044.
  5. Ryszard Engelking. General topology. Rev. and compl. ed., volume 6. Berlin: Heldermann Verlag, rev. and compl. ed. edition, 1989. Google Scholar
  6. Martin Escardó and Reinhold Heckmann. Topologies on spaces of continuous functions. Topology Proceedings, 26(2):545-564, 2001-2002. Google Scholar
  7. S. Franklin. Spaces in which sequences suffice II. Fundamenta Mathematicae, 61(1):51-56, 1967. URL: http://eudml.org/doc/214006.
  8. Jacques Grassin. Index sets in Ershov’s hierarchy. The Journal of Symbolic Logic, 39:97-104, March 1974. URL: https://doi.org/10.2307/2272349.
  9. Mathieu Hoyrup. Descriptive complexity on non-Polish spaces II, 2020. Preprint. URL: https://hal.inria.fr/hal-02483114.
  10. Alexander S. Kechris. Classical Descriptive Set Theory. Springer, January 1995. Google Scholar
  11. Shou Lin. A note on the Arens' space and sequential fan. Topology and its Applications, 81(3):185-196, 1997. URL: https://doi.org/10.1016/S0166-8641(97)00031-X.
  12. Tommy Norberg and Wim Vervaat. Capacities on non-Hausdorff spaces. Probability and Lattices, 110:133-150, 1997. Google Scholar
  13. Arno Pauly and Matthew de Brecht. Descriptive set theory in the category of represented spaces. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 438-449. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/LICS.2015.48.
  14. Yann Pequignot. A Wadge hierarchy for second countable spaces. Arch. Math. Log., 54(5-6):659-683, 2015. URL: https://doi.org/10.1007/s00153-015-0434-y.
  15. Luca Motto Ros, Philipp Schlicht, and Victor L. Selivanov. Wadge-like reducibilities on arbitrary quasi-Polish spaces. Mathematical Structures in Computer Science, 25(8):1705-1754, 2015. URL: https://doi.org/10.1017/S0960129513000339.
  16. Matthias Schröder. Admissible Representations for Continuous Computations. PhD thesis, FernUniversität Hagen, 2002. Google Scholar
  17. Matthias Schröder. Extended admissibility. Theor. Comput. Sci., 284(2):519-538, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00109-8.
  18. Matthias Schröder. The sequential topology on ℕ^ℕ^ℕ is not regular. Mathematical Structures in Computer Science, 19(5):943-957, 2009. URL: https://doi.org/10.1017/S0960129509990065.
  19. Matthias Schröder. A note on closed subsets in quasi-zero-dimensional qcb-spaces. Journal of Universal Computer Science, 16(18):2711-2732, September 2010. Google Scholar
  20. Victor L. Selivanov. Index sets in the hyperarithmetical hierarchy. Siberian Mathematical Journal, 25:474-488, 1984. URL: https://doi.org/10.1007/BF00968988.
  21. Victor L. Selivanov. Difference hierarchy in φ-spaces. Algebra and Logic, 43(4):238-248, July 2004. URL: https://doi.org/10.1023/B:ALLO.0000035115.44324.5d.
  22. Yoshio Tanaka. Theory of k-networks. Q. and A. in Gen. Top., 12:139-164, 1994. URL: https://ci.nii.ac.jp/naid/10010236971/en/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact