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
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
Host: Dandapani Sivakumar/Almaden/IBM e-mail: email@example.com