2 December 2002, Finite model property for guarded fragments, Ian Hodkinson

Abstract:
Guarded fragments are in some sense `modal-style' fragments of first-order logic. Introduced by Andréka, van Benthem and Németi in 1997, they have become very popular. They share nice properties with modal logic, such as decidability with reasonable complexity. The finite model property for the basic guarded fragment was established by Erich Grädel in 1999. Since then, several more results for stronger fragments have been proved. The proofs use a combinatorial theorem of Herwig, and recently this theorem has been strengthened in joint work with Martin Otto, permitting a simpler proof that the loosely guarded and packed (or clique-guarded) fragments have the finite model property. I will outline some of the ideas and history of this area of research.

For more information, contact Yde Venema (yde at science.uva.nl)