Regular Languages Defined with Generalized Quantifiers

We study an extension of first-order logic obtained by adjoining quantifiers that count with respect to an integer modulus. It is shown that the languages definable in this framework are precisely the regular languages whose syntactic monoids contain only solvable groups. We obtain an analogous result for regular ω-languages and establish some connections with complexity theory for fixed-depth families of circuits.

Authors

• H. Straubing
• D. Therien
• W. Thomas

Keywords

No keywords are indexed for this paper.