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