Résumé : Expressing properties of finite automata in variants of first-order logic Howard Straubing Boston College This is a survey of research going back more than 60 years on the power of first order logic, along with various restrictions and extensions, to express the behavior of finite automata operating on 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. This, along with a few other extensions (for example, to automata operating on trees) and some recent results and open probems, will be explored in the second part of the talk.

Dernière modification : Thursday 27 March 2025

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr