zbMATH — the first resource for mathematics

Regular languages defined with generalized quantifiers. (English) Zbl 0658.68098
Automata, languages and programming, Proc. 15th Int. Colloq., Tampere/Fin. 1988, Lect. Notes Comput. Sci. 317, 561-575 (1988).
[For the entire collection see Zbl 0639.00042.]
The paper characterizes those regular languages whose syntactic monoids contain only solvable groups. To this end first-order logic is extended by quantifiers of the form ‘there are exactly p elements modulo q such that...’. Imposing restrictions on the use of these quantifiers one obtains characterizations of those regular languages whose syntactic monoid is a solvable group, or is a solvable group with order divisible by previously given primes, or contains only solvable groups with orders divisible by previously given primes.
The first of the above four characterizations is then extended to the case of \(\omega\)-languages and, finally, some connections with the complexity of fixed-depth circuits are established.
Reviewer: L.Staiger

68Q45 Formal languages and automata
03B10 Classical first-order logic