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.2018.129
URN: urn:nbn:de:0030-drops-91336
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9133/
Go to the corresponding LIPIcs Volume Portal

Hoyrup, Mathieu ; Nava Saucedo, Diego ; Stull, Don M.

Semicomputable Geometry

pdf-format:
LIPIcs-ICALP-2018-129.pdf (0.5 MB)

Abstract

Computability and semicomputability of compact subsets of the Euclidean spaces are important notions, that have been investigated for many classes of sets including fractals (Julia sets, Mandelbrot set) and objects with geometrical or topological constraints (embedding of a sphere). In this paper we investigate one of the simplest classes, namely the filled triangles in the plane. We study the properties of the parameters of semicomputable triangles, such as the coordinates of their vertices. This problem is surprisingly rich. We introduce and develop a notion of semicomputability of points of the plane which is a generalization in dimension 2 of the left-c.e. and right-c.e. numbers. We relate this notion to Solovay reducibility. We show that semicomputable triangles admit no finite parametrization, for some notion of parametrization.

BibTeX - Entry

@InProceedings{hoyrup_et_al:LIPIcs:2018:9133,
  author =	{Mathieu Hoyrup and Diego Nava Saucedo and Don M. Stull},
  title =	{{Semicomputable Geometry}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{129:1--129:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9133},
  URN =		{urn:nbn:de:0030-drops-91336},
  doi =		{10.4230/LIPIcs.ICALP.2018.129},
  annote =	{Keywords: Computable set, Semicomputable set, Solovay reducibility, Left-ce real, Genericity}
}

Keywords: Computable set, Semicomputable set, Solovay reducibility, Left-ce real, Genericity
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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