1

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?

Community
  • 1
Pteromys
  • 895
  • 4
  • 13
  • 1
    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 09:01

0 Answers0