The parallel complexity of deterministic and probabilistic automata

A deterministic (probabilistic) automaton is said to be in TC0 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 TC0 is closed under homomorphism, sub-automaton, and alpha0-product operations. The class of k-state deterministic (probabilistic) automata is contained in TC0 if and only if k les 4 (k les 2), unless TC0 = NC1. Moreover, the possibility of ranking regular languages in TC0 is related to the group-structure of their syntactic monoid