Keynote Speaker

Speaker: Ronald Fagin
(IBM Almaden Research Center, San Jose, California) 		Ronald Fagin
 
Short Bio: Ronald Fagin is manager of the Foundations of Computer Science group at the IBM Almaden Research Center in San Jose, California. He received his B.A. in Mathematics from Dartmouth College and his Ph.D. in Mathematics from the University of California at Berkeley. His current research interests include applications of logic to computer science, database theory, finite model theory and reasoning about knowledge. Ronald Fagin has received numerous honours, e.g. the 2004 ACM SIGMOD Edgar F. Codd Innovations Award for his influential and lasting contributions to the principles and the practice of database systems over a period spanning nearly three decades, has published over 100 papers, and has co-authored a book on "Reasoning about Knowledge".
 
Title: Finite Model Theory and its Origins
 
Abstract:

Finite model theory is a study of the logical properties of finite mathematical structures. This talk gives an overview of how finite model theory arose, and of some work that sprang from that. This includes:

  • 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.
  • 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.
  • 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.
  • Descriptive complexity. Here we consider how complex a formula must be to express a given property.
The goal of this talk is to introduce the audience to the fascinating area of finite model theory.

 

Other keynote speakers at ACSW 2009 events include: Ian Foster (Argonne National Laboratory & University of Chicago), Mark Guzdial (College of Computing at Georgia Institute of Technology) and Andy Hopper (The Computer Laboratory, University of Cambridge).