# 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 - A PERSONAL PERSPECTIVE
## Abstract:

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.

dimacs-www@dmac.rutgers.edu
Document last modified on November 16, 1995