Finite monoids and the fine structure of <i>NC</i> ¹

Abstract

Recently a new connection was discovered between the parallel complexity class NC 1 and the theory of finite automata in the work of Barrington on bounded width branching programs. There (nonuniform) NC 1 was characterized as those languages recognized by a certain nonuniform version of a DFA. Here we extend this characterization to show that the internal structures of NC 1 and the class of automata are closely related. In particular, using Thérien's classification of finite monoids, we give new characterizations of the classes AC 0 , depth- k AC 0 , and ACC , the last being the AC 0 closure of the mod q functions for all constant q . We settle some of the open questions in [3], give a new proof that the dot-depth hierarchy of algebraic automata theory is infinite [8], and offer a new framework for understanding the internal structure of NC 1 .