Languages Defined with Modular Counting Quantifiers

We prove that a regular language defined by a boolean combination of generalized Σ1-sentences built using modular counting quantifiers can be defined by a boolean combination of Σ1-sentences in which only regular numerical predicates appear. The same statement, with “Σ1” replaced by “first-order, ” is equivalent to the conjecture that the nonuniform circuit complexity class ACC is strictly contained in NC 1. The argument introduces some new techniques, based on a combination of semigroup theory and Ramsey theory, which may shed some light on the general case.

Authors

• Howard Straubing

Keywords

No keywords are indexed for this paper.