Guarded Fragments: Current Trends and Applications (GF@25)

April 5-6, 2022, Fully Online 

The Guarded Fragment (GF) of was introduced in 1996 by Hajnal Andréka, Johan van Benthem and István Németi, as a decidable fragment of first-order logic that aims to explain the attractive algorithmic and model theoretic behavior of modal logic. It subsequently gave rise to a larger family of decidable guarded fragments of first-order logic and second-order logic. These guarded fragments are, up to today, still actively studied and used in various application domains across different areas of computer science and artificial intelligence (e.g., data management, knowledge representation).

This workshop is a celebration of the 25th anniversary of GF. It will show case recent results, bringing together different strands of research, and offering an opportunity for reflection.

Attendance is free. Please register here: https://forms.gle/FaEGSxQPec3jax4z7

 

Organizers:

Supported by the European Union’s Horizon 2020 research and innovation programme (MSCA-101031081: Logic and Learning: An Algebra and Finite Model Theory Approach (LLAMA)).

Schedule

All times listed in CET. All presentations are 30 minutes + discussion.

DAY 1: Tuesday April 5, 2022

DAY 2: Wednesday April 6, 2022

14:00

14:15 - 14:45

15:00 - 15:30

(break)

16:15 - 16:45

17:00 - 17:30

 

Opening

Michael Benedikt

When DB met GF

Georg Gottlob

Towards a good KR language: From guarded over weakly guarded to warded Datalog+/-.

Frank Wolter

Interpolants and Explicit Definitions in the Guarded Fragment of FO

Erich Grädel

Logic and Bisimulation for Guarded Teams

15:00 - 15:30

15:45 - 16:15

(break)

17:00 - 17:30

~17:45  

Emanuel Kieroński

Finite model reasoning in guarded fragments

Samson Abramsky

Comonadic semantics for guarded fragments

Johan van Benthem

Guarded Quantifiers and Generalized Semantics

Closing remarks

Zoom link: https://uva-live.zoom.us/j/89314056585

Speakers

Samson Abramsky

Professor of Computer Science, UCL

Comonadic semantics for guarded fragments

Michael Benedikt

Professor of Computer Science, Oxford University

When DB met GF

The Guarded Fragment generalizes the modal decidability paradigm to higher-arity signatures. In retrospect, it seems natural for GF to have impact within databases, since there has always been a focus in database research on analysis and evaluation of first-order formulas in arbitrary arity.  But the path to recognizing the relevance of GF had many detours. This talk overviews how and why reasoning with GF and its subfragments emerged as an important topic in data management research.

Johan van Benthem

University Professor, emeritus, University of Amsterdam;

Professor, Stanford University; Professor, Tsinghua University

Guarded Quantifiers and Generalized Semantics

I will recall some of the history of the guarded fragment as bringing together algebraic and modal traditions. Next I consider dualities between looking at fragments of logical languages or generalizing their semantics as ways of bringing down SAT complexity. I end with some challenging encounters with guarding by the ABN authors in the years after the initial paper.

Georg Gottlob

Professor of Computing Science, Oxford University

Towards a good KR language: From guarded over weakly guarded to warded Datalog+/-.

This is the story of the search for a good language for knowledge representation (KR). We were looking for a tractable language for ontological reasoning and various other reasoning and query-answering tasks. We first discuss a very simple language, guarded Datalog+/-, which are guarded TGDs with negative constraints. Unfortunately, this language is not well-suited for joins, so we extend it and obtain weakly guarded Datalog+/-. This powerful language contains full Datalog and is very expressive: it captures (that is, exactly expresses) PSPACE. Unfortunately., this also means it has a high query complexity. Consequently we reduced it again, to get Warded Datalog+/-, a tractable language that still contains classical Datalog but also has somewhat restricted possibilities of using existential quantifiers in rule heads for ontological reasoning and for several other useful tasks I will illustrate.

Erich Grädel

Professor, RWTH Aachen

Logic and Bisimulation for Guarded Teams

Emanuel Kieroński

Institute of Computer Science, University of Wrocław

Finite model reasoning in guarded fragments

Starting from the fundamental theorem that the basic guarded fragment has the finite model property, I will review some results concerning finite model reasoning in guarded logics. I will mention the finite model property for the loosely guarded fragment, the guarded negation fragment and the triguarded fragment, as well as I will make a few comments on cases where the finite model property fails, in particular considering reasoning under semantic constraints.

Frank Wolter

Professor, University of Liverpool

Interpolants and Explicit Definitions in the Guarded Fragment of FO

I will discuss recent work with Jean Christoph Jung on the problem of deciding the existence of Craig interpolants and explicit definitions in the guarded fragment of first-order logic. Applications of Craig interpolants to the logical separation problem for positive and negative data examples under the open world assumption will be discussed and I will also relate the Craig interpolant existence problem to the uniform interpolant existence problem. I will close with a few interesting open problems.