First Order Logics Extended With Counting Quantifiers

In this talk, we shall look at logics over words. It is known that first order logic (FO) with an order relation, <, defines exactly the set of all aperiodic regular languages. This class of languages is known to be a strict subset of regular languages. The difficulty of first order logic is its inability to count.  Can we overcome this if we allow other relations?  We will see that an addition predicate, +, is not very helpful. What about multiplication? Suddenly we see that one can count to log of the word length.  Hence, the "Crane Beach conjecture" turns out to be false for this logic. Will adding extra predicates help us count more? We see that no predicate can  enhance the counting capability further. For example, the language L="set of all words with even number of a's" is not definable in FO with any set of relations. How can we enhance the counting capability? Introducing modulo counting quantifiers (or other regular quantifiers) is one way. We will see that these quantifiers interactwith addition and multiplication in highly non-trivial ways giving some interesting  results and lots of open problems. Many of these open problems closely relate to those in circuit complexity.