Access Restriction

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

   Open content in new tab
Source: ACM Digital Library