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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.