Languages Defined with Modular Counting Quantifiers

AbstractWe 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 NC1. 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