What are Guarded Negation Logics?
The Guarded Negation Fragment (GNFO) is a decidable fragment of first-order logic that extends the Guarded Fragment (GF), and that includes unions of conjunctive queries, as well as a restricted form of negation that suffices for expressing some common uses of negation in SQL queries, and a large class of integrity constraints. The extension of GNFO with least fixpoint operator, known as GNFP, is decidable as well. Besides being computationally well behaved, GNFO and GNFP are model-theoretically well behaved. In particular, many classic results from the model theory of first-order logic, such as the Craig interpolation theorem, have effective analogues for guarded negation logics. The guarded negation logics GNFO and GNFP have found applications in the areas of data management and knowledge representation.
Researchers
People who have contributed to the study of guarded negation logics include
- Vince Barany (Google, Inc.)
- Michael Benedikt (Oxford University)
- Balder ten Cate (UC Santa Cruz)
- Thomas Colcombet (LIAFA, Université Denis Diderot – Paris 7)
- Martin Otto (TU Darmstadt)
- Luc Segoufin (INRIA, ENS Cachan)
- Michael Vanden Boom (Oxford University)
Publications
- Luc Segoufin, Balder ten Cate (2013). Unary negation. Logical Methods in Computer Science 9(3): 25, 46 pages. Extended version of STACS 2011 paper.
- Vince Bárány, Balder ten Cate and Luc Segoufin (2015). Guarded negation. Journal of the ACM 62(3): 22. Extended version of ICALP 2011 paper.
- Vince Bárány, Balder ten Cate and Martin Otto (2012). Queries with Guarded Negation. Proceedings of VLDB 2012.
- Martin Otto (2013). Expressive completeness through logically tractable models. Annals of Pure and Applied Logic 164(12): 1418-1453.
- Vince Bárány, Michael Benedikt, Balder ten Cate (2013). Rewriting Guarded Negation Queries. Proceedings of MFCS 2013.
- Michael Benedikt, Balder ten Cate and Michael Vanden Boom (2014). Effective Interpolation and Preservation in Guarded Logics. Proceedings of LICS 2014.
- Michael Benedikt, Thomas Colcombet, Balder ten Cate and Michael Vanden Boom (2015). The Complexity of Boundedness for Guarded Logics. Proceedings of LICS 2015.
- Michael Benedikt, Balder ten Cate and Michael Vanden Boom (2015). Interpolation with Decidable Fixpoint Logics. Proceedings of LICS 2015.
Applications of Guarded-Negation Logics in Data-Management and Knowledge Representation
- Vince Bárány, Michael Benedikt, Pierre Bourhis (2013). Access patterns and integrity constraints revisited. Proceedings of ICDT 2013.
- Pierre Bourhis, Michael Morak, Andreas Pieris (2013). The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules. Proceedings of IJCAI 2013.
- Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, Frank Wolter (2014). Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP. ACM Transactions on Database Systems 39(4): 33:1-33:44. Extended version of PODS 2013 paper.
Further Dissemination
- Querying and Reasoning Under Expressive Constraints (Dagstuhl Seminar 14331). A workshop organized in 2014 by Michael Benedikt, Balder ten Cate, and Carsten Lutz, bringing together researchers from the areas of data management, knowledge representation, and computational logic.
- Modern Database Dependency Theory. A week-long ESSLLI 2014 summer school course taught by Michael Benedikt and Balder ten Cate.
If there are items missing from the above list please let me know, and they will be added.