Moshe Y. Vardi

Rice University

Computational Model Theory

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

June 21, 2:30 p.m.

Abstract:

Model theory and recursion theory are two distinct and quite separate branches in mathematical logic. On the other hand, finite-model theory and complexity theory, which constitute their analogues in computer science, are, in contrast, intimately interrelated, giving together rise to computational model theory. Underlying this theory is the extension of first-order logic with iteration constructs, in order to make the logic "computational". These iterative logics can be viewed as effective fragments of infinitary finite-variable logic, whose expressive power can be captured by means of pebble games. Alternatively, these logics can be viewed as complexity-bounded classes of relational machines, which are Turing machines equiped with a relational store. Thus, characterizing the expressive power of these logics is equivalent to understanding the relationship between complexity classes such as PTIME and PSPACE.

In this expository talk the speaker will survey 15 years of research in this area.