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?
Is there a signature of a first-order language that characterize the class of regular languages?
reference request;lo.logic;regular language;finite model theory