Journal of Symbolic Logic 83 (4):1307-1344 (2018)

Authors
Michael Benedikt
University of Texas at Austin
Abstract
The Guarded Negation Fragment is a fragment of first-order logic that contains all positive existential formulas, can express the first-order translations of basic modal logic and of many description logics, along with many sentences that arise in databases. It has been shown that the syntax of GNFO is restrictive enough so that computational problems such as validity and satisfiability are still decidable. This suggests that, in spite of its expressive power, GNFO formulas are amenable to novel optimizations. In this article we study the model theory of GNFO formulas. Our results include effective preservation theorems for GNFO, effective Craig Interpolation and Beth Definability results, and the ability to express the certain answers of queries with respect to a large class of GNFO sentences within very restricted logics.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2018.64
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,078
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Modal Logic Over Finite Structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
Modal and Guarded Characterisation Theorems Over Finite Transition Systems.Martin Otto - 2004 - Annals of Pure and Applied Logic 130 (1-3):173-205.
Expressive Completeness Through Logically Tractable Models.Martin Otto - 2013 - Annals of Pure and Applied Logic 164 (12):1418-1453.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Guarded Negation.Balder ten Care - 2012 - In Thomas Bolander, Torben Braüner, Silvio Ghilardi & Lawrence Moss (eds.), Advances in Modal Logic, Volume 9. CSLI Publications. pp. 183-184.
Guarded Fragments with Constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic 14 (3):281-288.
Guarded Fragments with Constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic, Language and Information 14 (3):281-288.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Modal and Guarded Characterisation Theorems Over Finite Transition Systems.Martin Otto - 2004 - Annals of Pure and Applied Logic 130 (1-3):173-205.
Negation And Contradiction.Richard Routley Val Routley, Richard Sylvan & Richard Routley - 1985 - Revista Columbiana de Mathematicas:201 - 231.
Empirical Negation.Michael De - 2013 - Acta Analytica 28 (1):49-69.
Expressive Completeness Through Logically Tractable Models.Martin Otto - 2013 - Annals of Pure and Applied Logic 164 (12):1418-1453.

Analytics

Added to PP index
2018-12-22

Total views
13 ( #765,908 of 2,498,913 )

Recent downloads (6 months)
1 ( #421,180 of 2,498,913 )

How can I increase my downloads?

Downloads

My notes