1988/10/01 by David A. Mix Barrington, Denis Thérien · 5 citations
Computer Science · Mathematics · #semigroups and automata theory #Complexity and Algorithms in Graphs #Formal Methods in Verification #Connection (principal bundle) #Closure (psychology) #Hierarchy #Branching (polymer chemistry) #Mathematics #Bounded function #Complexity class #Algebraic number #Discrete mathematics #Constant (computer programming) #Automaton #Class (philosophy) #Algebraic theory #Combinatorics #Pure mathematics #Computer science #Time complexity #Geometry #Theoretical computer science #Mathematical analysis
paper · pdf · doi:10.1145/48014.63138
openalex publication_date 1988/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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 .