Finite monoids and the fine structure of NC 1

Abstract

Recently a new connection was discovered between the parallel complexity class NC ¹ and the theory of finite automata in the work of Barrington on bounded width branching programs. There (nonuniform) NC ¹ 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 ¹ 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 ⁰ , depth- k AC ⁰ , and ACC , the last being the AC ⁰ 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 ¹ .