Logic List Mailing Archive

Talk at IBM Almaden (fwd)

FAGIN TO SPEAK AT ALMADEN
 

Topic:         Finite-Model Theory -- a Personal Perspective

Speaker:       Ronald Fagin

Date:          Friday, June 29, 2001
 
Time:          1:00 PM - 2:30 PM
 
Location:      Room B1-413, IBM Almaden Research Center

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.

In recent years, there has been a re-awakening of interest in
finite-model theory.  One goal of this talk is to help "fan the
flames" of interest, by introducing the audience to this fascinating
area.


Host: Dandapani Sivakumar/Almaden/IBM    e-mail: danda@us.ibm.com