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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Nov 21 '16 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.