DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2018.8

Safety, Absoluteness, and Computability

Authors: Arnon Avron, Shahar Lev, and Nissan Levi

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

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.

Cite as

Arnon Avron, Shahar Lev, and Nissan Levi. Safety, Absoluteness, and Computability. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{avron_et_al:LIPIcs.CSL.2018.8,
  author =	{Avron, Arnon and Lev, Shahar and Levi, Nissan},
  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 =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.8},
  URN =		{urn:nbn:de:0030-drops-96754},
  doi =		{10.4230/LIPIcs.CSL.2018.8},
  annote =	{Keywords: Dependent Safety, Computability, Absoluteness, Decidability, Domain Independence}
}

Search Results

Documents authored by Lev, Shahar

Safety, Absoluteness, and Computability

Abstract

Cite as

Thanks for your feedback!

Could not send message