Combinatorial Games in Finite Model Theory
Section: Logic and Computation
Combinatorial games give rise to a powerful and versatile method
for analyzing logics on classes of finite structures. The aim of this
course is to present the main combinatorial games used in finite model
theory, give a representative sample of their numerous applications,
and also derive connections between combinatorial games, database
theory, constraint satisfaction, and computational complexity.
- Lecture 1: Ehrenfeucht-Fraïsse games; applications to the
expressive power of first-order logic.
- Lecture 2: Games for existential second-order logic;
connections with the NP = coNP problem; applications to the expressive
power of monadic existential second-order logic.
- Lecture 3: Pebble games and finite-variable logics;
applications to the expressive power of fixed-point logics;
applications to 0-1 laws.
- Lecture 4: Existential pebble games and Datalog; applications to
the study of constraint satisfaction.
- Lecture 5: Computational complexity of Ehrenfeucht-Fraïsse
games and of pebble games; algorithms for computing winning
The prerequisites for this course are familiarity with the basic
concepts of first-order logic and rudimentary knowledge of
computational complexity (polynomial-time computability and
- P. Kolaitis and M. Vardi, Conjunctive-Query
Containment and Constraint Satisfaction
- P. Kolaitis and M. Vardi, A Game-Theoretic Approach to
Phokion G. Kolaitis
Computer Science Department
University of California, Santa Cruz
Santa Cruz, CA 95064, USA