1 Search Results for "Nava Saucedo, Diego"

Document
DOI: 10.4230/LIPIcs.ICALP.2018.129
Semicomputable Geometry

Authors: Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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.
Cite as

Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull. Semicomputable Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 129:1-129:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hoyrup_et_al:LIPIcs.ICALP.2018.129,
  author =	{Hoyrup, Mathieu and Nava Saucedo, Diego and Stull, Don M.},
  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 =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.129},
  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}
}
  • Refine by Author
  • 1 Hoyrup, Mathieu
  • 1 Nava Saucedo, Diego
  • 1 Stull, Don M.

  • Refine by Classification
  • 1 Theory of computation → Computability

  • Refine by Keyword
  • 1 Computable set
  • 1 Genericity
  • 1 Left-ce real
  • 1 Semicomputable set
  • 1 Solovay reducibility

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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 Imprint Privacy Contact