What Can You Say in First-Order Logic? An Algebraic Perspective
Time and place
12:15 PM on Thursday, March 15th, 2012;
Howard Straubing (Boston College)
Abstract
Note: this is a combined event, joint with the Math-CS Colloquium. There will be two talks, with a five-minute break in between: the first half is accessible to undergraduates in Math and CS, and the second half is aimed at the specialists.
Abstract:
We ask what properties of finite structures (e.g., labeled strings, trees, graphs…) are expressible in a simple logical language—usually some variant of first-order logic. Questions about the expressive power of first-order logic belong to model theory. Historically, model theory drew much of it inspiration from the foundations of mathematics, and concentrated on infinite structures. The more recent growth of interest in finite model theory comes from computer science (computer-aided verification, database theory, and computational complexity). Classical model- theoretic techniques often fail for finite structures, and new methods have had to be developed.
In the first part of this talk I will exhibit what has by now become a ‘classical’ method of finite model theory---Ehrenfeucht-Fraïssé games---and use it to show that some properties of finite strings are inexpressible in first-order logic. We then bring the algebra of finite semigroups into the picture, and show how it gives a definitive answer to this kind of question: We obtain an effective characterization of all properties of finite strings definable in several versions of first-order logic.
In the second part of the talk I will discuss some recent research aimed at extending this theory from strings to trees. Here most of the basic questions remain open, and we are only beginning to develop the outlines of an algebraic theory equipped to answer them.
