# Is there a signature of a first-order language that characterize the class of regular languages?

A previous question on this site was about extending the first-order logic with logical constants (quantifiers, fixed-point operators, etc.) to obtain a logical characterization of the class of regular languages.

Alternatively, one could try to get a characterization by expanding the signature of the first-order language, i.e., by allowing new kind of atomic formulas. For example, in Straubing's Finite Automata, Formal Logic and Circuit Complexity, first-order logic with arbitrary number predicates is considered, and it is shown that it characterize the circuit complexity class AC$^0$. Can a similar thing be done to the class of regular languages? Or is it known that this is simply impossible?

• You already have the answer: no matter what you put in the signature, first-order definable classes of models are recognizable in AC^0, hence cannot express non-AC^0 regular languages. What else do you want to know? – Emil Jeřábek Nov 21 '16 at 9:01