\input zb-basic
\input zb-ioport
\iteman{io-port 05617723}
\itemau{Kouck\'y, Michal}
\itemti{Circuit complexity of regular languages.}
\itemso{Theory Comput. Syst. 45, No. 4, 865-879 (2009).}
\itemab
Summary: We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in $\text{AC}^{0}$ and $\text{ACC}^{0}$ are all computable by almost linear size circuits, extending the result of {\it A. K. Chandra, S. Fortune} and {\it R. Lipton} [J. Comput. Syst. Sci. 30, 222--234 (1985; Zbl 0604.68051)]. As a consequence we obtain that in order to separate $\text{ACC}^{0}$ from $\text{NC}^{1}$ it suffices to prove for some $\epsilon >0$ an $\Omega (n ^{1+\epsilon })$ lower bound on the size of $\text {ACC}^{0}$ circuits computing certain $\text{NC}^{1}$-complete functions.
\itemrv{~}
\itemcc{}
\itemut{regular languages; circuit complexity; upper and lower bounds}
\itemli{doi:10.1007/s00224-009-9180-z}
\end