Guarded Negation

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.


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)


Applications of Guarded-Negation Logics in Data-Management and Knowledge Representation

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.

If there are items missing from the above list please let me know, and they will be added.

Recent Posts