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

Avron, Arnon ; Lev, Shahar ; Levi, Nissan

Safety, Absoluteness, and Computability

pdf-format:
LIPIcs-CSL-2018-8.pdf (0.4 MB)

Abstract

The semantic notion of dependent safety is a common generalization of the notion of absoluteness used in set theory and the notion of domain independence used in database theory for characterizing safe queries. This notion has been used in previous works to provide a unified theory of constructions and operations as they are used in different branches of mathematics and computer science, including set theory, computability theory, and database theory. In this paper we provide a complete syntactic characterization of general first-order dependent safety. We also show that this syntactic safety relation can be used for characterizing the set of strictly decidable relations on the natural numbers, as well as for characterizing rudimentary set theory and absoluteness of formulas within it.

BibTeX - Entry

@InProceedings{avron_et_al:LIPIcs:2018:9675,
  author =	{Arnon Avron and Shahar Lev and Nissan Levi},
  title =	{{Safety, Absoluteness, and Computability}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9675},
  URN =		{urn:nbn:de:0030-drops-96754},
  doi =		{10.4230/LIPIcs.CSL.2018.8},
  annote =	{Keywords: Dependent Safety, Computability, Absoluteness, Decidability, Domain Independence}
}

Keywords: Dependent Safety, Computability, Absoluteness, Decidability, Domain Independence
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

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