License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.8
URN: urn:nbn:de:0030-drops-118694
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11869/
Go to the corresponding LIPIcs Volume Portal

Callard, Antonin ; Hoyrup, Mathieu

Descriptive Complexity on Non-Polish Spaces

pdf-format:
LIPIcs-STACS-2020-8.pdf (0.5 MB)

Abstract

Represented spaces are the spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. We prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets. We prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. We study the larger class of coPolish spaces, showing that their representation does not always preserve the complexity of sets, and we relate this mismatch with the sequential aspects of the space. We study in particular the space of polynomials.

BibTeX - Entry

@InProceedings{callard_et_al:LIPIcs:2020:11869,
  author =	{Antonin Callard and Mathieu Hoyrup},
  title =	{{Descriptive Complexity on Non-Polish Spaces}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11869},
  URN =		{urn:nbn:de:0030-drops-118694},
  doi =		{10.4230/LIPIcs.STACS.2020.8},
  annote =	{Keywords: Represented space, Computable analysis, Descriptive set theory, CoPolish spaces}
}

Keywords: Represented space, Computable analysis, Descriptive set theory, CoPolish spaces
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI