# Regular versus TC0

According to the Complexity Zoo, $$\mathsf{Reg} \subseteq \mathsf{NC^1}$$ and we know that $$\mathsf{Reg}$$ cannot count so $$\mathsf{TC^0} \not\subseteq \mathsf{Reg}$$. However it doesn't say if $$\mathsf{Reg} \subseteq \mathsf{TC^0}$$ or not. Since we don't know $$\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$$ we also don't know $$\mathsf{Reg} \not\subseteq \mathsf{TC^0}$$.

Is there a candidate for a problem in $$\mathsf{Reg}$$ that is not in $$\mathsf{TC^0}$$?

Is there a conditional result implying that $$\mathsf{Reg} \not\subseteq \mathsf{TC^0}$$, e.g. if $$\mathsf{NC^1} \not\subseteq \mathsf{TC^0}$$ then $$\mathsf{Reg} \not\subseteq \mathsf{TC^0}$$?

Take $S_5$ as alphabet and $$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$ Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}^0$ reduction (and even with a more restrictive reduction actually).

In particular this shows that regular languages are not in $\textrm{TC}^0$ if $\textrm{TC}^0 \subsetneq \textrm{NC}^1$. By using semigroups theory (see the book of Straubing [1] for more details), we obtain that if $\textrm{ACC}^0$ is strictly in $\textrm{NC}^1$ then all regular languages are either $\textrm{NC}^1$-complete or $\textrm{ACC}^0$.

[1] Straubing, Howard (1994). "Finite automata, formal logic, and circuit complexity". Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1"

• Furthermore, if ACC$^0$ is not "strictly in NC$^1$ then all regular languages are" in ACC$^0$ anyway. $\;\;\;\;$
– user6973
Jan 3, 2016 at 1:58

Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals uniform width-5 branching programs). Thus, any such language is not in $\mathrm{TC}^0$ unless $\mathrm{TC}^0=\mathrm{NC}^1$.

My favorite $\mathrm{NC}^1$-complete regular expression is $((a|b)^3(ab^∗a|b))^∗$ (this is actually an encoding of $S_5$, as in C.P.'s answer).

• what is a syntactic monoid? Jan 2, 2016 at 18:28
• Warning of confusing terminology: in this context, a monoid is said to be unsolvable if it contains an unsolvable group as a subsemigroup, not necessarily as a submonoid. Jan 2, 2016 at 18:40
• My favourite NC^1-complete regular expression is $((a|b)^3(ab^*a|b))^*$ (this is actually an encoding of S_5, as in C.P.'s answer). Jan 2, 2016 at 18:55
• Another example, less concise but easier to understand: $$((a+b)(ab^*ab^*ab^*a+b))^*$$ the 'a' act as the cycle (1 2 3 4 5), the "b" act as the permutation (1 2), and those two group element are known to generate $S-5$.
– C.P.
Jan 3, 2016 at 8:35
• @MichaelCadilhac: $a$ acts as $(1,2,3,4,5)$, and $b$ as $(1,2,3,4)$. These generate $S_5$ as $ba^{-1}$ is a transposition. Jan 3, 2016 at 10:40