### Finite monoids and the fine structure of $\textit{NC}1$Finite monoids and the fine structure of $\textit{NC}1$

Access Restriction
Subscribed

 Author Barrington, David A Mix ♦ Thrien, Denis Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1988 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Recently a new connection was discovered between the parallel complexity class $\textit{NC}1$ and the theory of finite automata in the work of Barrington on bounded width branching programs. There (nonuniform) $\textit{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 $\textit{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 $\textit{AC}0,$ $depth-\textit{k}$ $\textit{AC}0,$ and $\textit{ACC},$ the last being the $\textit{AC}0$ closure of the mod $\textit{q}$ functions for all constant $\textit{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 $\textit{NC}1.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1988-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 35 Issue Number 4 Page Count 12 Starting Page 941 Ending Page 952

#### Open content in new tab

Source: ACM Digital Library