Abstract: This is a survey of research going back approximately 60 years (beginning with an unpublished research report by Robert McNaughton) on the power of first order logic, along with various restrictions and extensions, to express properties of strings over a finite alphabet. 'Restrictions and extensions' here means modifying the set of atomic formulas, bounding the quantifier depth, bounding the number of bound variables, etc. We want to be able to determine when a particular property (given in some other formalism, for example by a finite automaton) is expressible in the variant of first-order logic under study.
When the atomic formulas are restricted in such a way that only regular languages can be defined, there is an intricate mathematical apparatus, based in the algebraic theory of finite semigroups, that provides very precise answers to these questions. This will be the subject of the first part of the talk.
There are strong connections, known since the 1980's, between this theory and questions about the complexity of fixed depth circuit families whose gates have unbounded fan-in. There is also an elegant generalization of the algebraic theory to automata operating on labeled trees rather than strings. It was hoped that, in the first case, this would lead to new methods for proving circuit lower bounds, and, in the second, settle some questions about properties of trees expressible in first-order and temporal logic. Neither of these approaches has (so far!) delivered the hoped-for results, but they have left some tantalizing open problems, which will be the subject of the second part of the talk.
Bio: Howard Straubing graduated from the University of Michigan, and received a Ph.D. in Mathematics from the University of California at Berkeley, after which he taught at Reed College in Portland, Oregon. Since 1984, he has been masquerading as a 'computer scientist' at Boston College, where, despite the thin disguise, no one appears to notice, or care. Most of his research has been devoted to the matters raised in the abstract for this talk, both the giddy heights and the heartbreaking disappointments.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.