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.ICALP.2020.132
URN: urn:nbn:de:0030-drops-125395
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12539/
Go to the corresponding LIPIcs Volume Portal

Hoyrup, Mathieu

Descriptive Complexity on Non-Polish Spaces II

pdf-format:
LIPIcs-ICALP-2020-132.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{hoyrup:LIPIcs:2020:12539,
  author =	{Mathieu Hoyrup},
  title =	{{Descriptive Complexity on Non-Polish Spaces II}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{132:1--132:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12539},
  URN =		{urn:nbn:de:0030-drops-125395},
  doi =		{10.4230/LIPIcs.ICALP.2020.132},
  annote =	{Keywords: Represented space, Computable analysis, Descriptive set theory, Scott topology}
}

Keywords: Represented space, Computable analysis, Descriptive set theory, Scott topology
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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