Moshe Y. Vardi
Computational Model Theory
- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- June 21, 2:30 p.m.
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.