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.MFCS.2019.48
URN: urn:nbn:de:0030-drops-109928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10992/
Go to the corresponding LIPIcs Volume Portal

Hoyrup, Mathieu ; Stull, Donald M.

Semicomputable Points in Euclidean Spaces

pdf-format:
LIPIcs-MFCS-2019-48.pdf (0.5 MB)

Abstract

We introduce the notion of a semicomputable point in R^n, defined as a point having left-c.e. projections. We study the range of such a point, which is the set of directions on which its projections are left-c.e., and is a convex cone. We provide a thorough study of these notions, proving along the way new results on the computability of convex sets. We prove realization results, by identifying computability properties of convex cones that make them ranges of semicomputable points. We give two applications of the theory. The first one provides a better understanding of the Solovay derivatives. The second one is the investigation of left-c.e. quadratic polynomials. We show that this is, in fact, a particular case of the general theory of semicomputable points.

BibTeX - Entry

@InProceedings{hoyrup_et_al:LIPIcs:2019:10992,
  author =	{Mathieu Hoyrup and Donald M. Stull},
  title =	{{Semicomputable Points in Euclidean Spaces}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10992},
  URN =		{urn:nbn:de:0030-drops-109928},
  doi =		{10.4230/LIPIcs.MFCS.2019.48},
  annote =	{Keywords: Semicomputable point, Left-c.e. real, Convex cone, Solovay reducibility, Genericity}
}

Keywords: Semicomputable point, Left-c.e. real, Convex cone, Solovay reducibility, Genericity
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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