Ronald Fagin

DIMACS Center - Rutgers University
CoRE Building, 1st Floor Lecture Hall
Piscataway, New Jersey
Friday, January 19, 1996
11:00 AM

Topic of Discussion



Finite-model theory is a study of the logical properties of finite mathematical structures. This talk gives an overview, including:

(1) Differences between the model theory of finite structures and infinite structures. Most of the classical theorems of logic fail for finite structures, which gives us a challenge to develop new concepts and tools, appropriate for finite structures.

(2) The relationship between finite-model theory and complexity theory. Surprisingly enough, it turns out that in some cases, we can characterize complexity classes (such as NP) in terms of logic, without using any notion of machine, computation, or time.

(3) Zero-one laws. There is a remarkable phenomenon, which says that certain properties (such as those expressible in first-order logic) are either almost surely true or almost surely false.

(4) Descriptive complexity. Here we consider how complex a formula must be to express a given property.

This talk will be a self-contained introduction to the fascinating area of finite-model theory.

About the Speaker:

Ronald Fagin is manager of the Foundations of Computer Science group at the IBM Almaden Research Center in San Jose, California. Most of his research has centered on applications of logic to computer science. In particular, he has done research on finite-model theory, on the theory of relational databases, and on theories of knowledge and belief. He has received four IBM Outstanding Innovation Awards for his contributions to relational database theory, extendible hashing, reasoning about knowledge, and zero-one laws. He was co-recipient (with Joseph Halpern) of the MIT Press Publisher's Prize for the Best Paper at the 1985 International Joint Conference on Artificial Intelligence. He co-authored a book, jointly with Joseph Halpern, Yoram Moses, and Moshe Vardi, on "Reasoning about Knowledge", that was published in 1995 by MIT Press.

Document last modified on November 16, 1995