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)). |
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
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. |
