Combinatorial Games in Finite Model Theory

Phokion Kolaitis
Section: Logic and Computation
Level: Advanced


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.

Course Outline


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



Phokion G. Kolaitis
Computer Science Department
University of California, Santa Cruz
Santa Cruz, CA 95064, USA
phone: +1-831-459-4768
fax: +1-831-459-4829