29th European Summer School in Logic, Language, and Information
University of Toulouse (France), 17-28 July, 2017

Complexity of Two-Variable First-Order Logics

Emanuel Kieronski, Lidia Tendera

Logic and Computation (Introductory)

First week, from 14:00 to 15:30


In this course we explore recent work in the quest for expressive fragments of first-order logics with good algorithmic properties, special attention giving to the two-variable fragment and its intersection with the guarded fragment. While tracing the boundary between decidable and undecidable fragments we describe their power, limitations, similarities and differences in order to stress out key properties responsible for their good or bad behaviour. We also highlight tools and techniques that have proven most effective for designing optimal algorithms for solving the satisfiability or the finite satifiability problems.