Regular languages in NC1

Abstract

We give several characterizations, in terms of formal logic, semigroup theory, and operations on languages, of the regular languages in the circuit complexity class AC0, thus answering a question of Chandra, Fortune, and Lipton. As a by-product, we are able to determine effectively whether a given regular language is in AC0 and to solve in part an open problem originally posed by McNaughton. Using recent lower-bound results of Razborov and Smolensky, we obtain similar characterizations of the family of regular languages recognized by constant-depth circuit families that include unbounded fan-in mod p addition gates for a fixed prime p along with unbounded fan-in boolean gates. We also obtain logical characterizations for the class of all languages recognized by nonuniform circuit families in which mod m gates (where m is not necessarily prime) are permitted. Comparison of this characterization with our previous results provides evidence for a conjecture concerning the regular languages in this class. A proof of this conjecture would show that computing the bit sum modulo p, where p is a prime not dividing m, is not AC0-reducible to addition mod m, and thus that MAJORITY is not AC0-reducible to addition mod m.