Back

Combinatorial Games in Finite Model Theory

Phokion Kolaitis
Section: Logic and Computation
Level: Advanced

Description

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

Prerequisites

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

Materials

Lecturers

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