The Parallel Complexity of Deterministic and Probabilistic Automata
Carlo Mereghetti, Beatrice Palano · Journal of automata, languages and combinatorics · 2002
A deterministic (probabilistic) automaton is said to be in $\TC^0$ whenever its transitions (stochastic event) can be computed by threshold circuits of polynomial size and constant depth. Here, we prove that: -- The class of deterministic automata in $\TC^0$ is closed under homomorphism, subautomaton, and $\alpha_0$-product operations. -- The class of $k$-state deterministic (probabilistic) automata is contained in $\TC^0$ if and only if $k\leq 4$ ($k \leq 2$), unless $\TC^0=\NC^l$. Moreover, the possibility of ranking regular languages in $\TC^0$ is related to the group-structure of their syntactic monoid.