<p>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$.</p>

<p>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).</p>

CC BY-SA 3.0
2016-01-02T18:28:31.557Z
what is a syntactic monoid?
Turbo
CC BY-SA 3.0
2016-01-02T18:34:35.883Z
https://en.wikipedia.org/wiki/Syntactic_monoid
Emil Jeřábek
CC BY-SA 3.0
2016-01-02T18:40:46.660Z
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.
Emil Jeřábek
CC BY-SA 3.0
2016-01-02T18:55:37.323Z
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).
Emil Jeřábek
CC BY-SA 3.0
2016-01-02T19:00:46.063Z
So basically asking if there is a DFA not implementable in TC0 or in other words is graph reachability in TC0 right?
Turbo
CC BY-SA 3.0
2016-01-03T05:29:28.033Z
Would you mind indicating how $((a|b)^3(ab^*a|b))^*$ encodes $S_5$?  Thanks!
Michaël Cadilhac
CC BY-SA 3.0
2016-01-03T08:35:14.997Z
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.
CC BY-SA 3.0
2016-01-03T10:40:06.027Z
@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.
Emil Jeřábek
CC BY-SA 4.0
2021-06-06T12:25:21.553Z
@EmilJeřábek 1) If $REG$ is complete for $NC^1$ then because $TC^0$ is in $NC^1$ it seems $REG$ can count. Is it correct? 2) If $TC^0\neq NC^1$ is $ACC^0\neq TC^0$ unconditionally or is it possible $ACC^0=TC^0\neq NC^1$ is still allowed?
Turbo
CC BY-SA 3.0
2016-01-02T18:21:18.730Z
2016-01-02T19:27:40.010Z
2016-01-02T19:27:40.010Z
Emil Jeřábek
<p>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). </p>

<p>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$.</p>

<p>[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. </p>

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

CC BY-SA 3.0
2016-01-02T18:21:00.493Z
2016-01-02T18:26:14.157Z
2016-01-02T18:26:14.157Z
C.P.
<p>According to <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg" rel="noreferrer">the Complexity Zoo</a>,
<span class="math-container">$\mathsf{Reg} \subseteq \mathsf{NC^1}$</span> and
we know that <span class="math-container">$\mathsf{Reg}$</span> cannot count so <span class="math-container">$\mathsf{TC^0} \not\subseteq \mathsf{Reg}$</span>.
However it doesn't say if <span class="math-container">$\mathsf{Reg} \subseteq \mathsf{TC^0}$</span> or not. Since we don't know <span class="math-container">$\mathsf{NC^1}\not\subseteq\mathsf{TC^0}$</span> we also don't know <span class="math-container">$\mathsf{Reg} \not\subseteq \mathsf{TC^0}$</span>.</p>
<blockquote>
<p>Is there a candidate for a problem in <span class="math-container">$\mathsf{Reg}$</span> that is not in <span class="math-container">$\mathsf{TC^0}$</span>?</p>
<p>Is there a conditional result implying that <span class="math-container">$\mathsf{Reg} \not\subseteq \mathsf{TC^0}$</span>, e.g. if <span class="math-container">$\mathsf{NC^1} \not\subseteq \mathsf{TC^0}$</span> then <span class="math-container">$\mathsf{Reg} \not\subseteq \mathsf{TC^0}$</span>?</p>
</blockquote>

<cc.complexity-theory><fl.formal-languages><automata-theory><circuit-complexity><regular-language>
Regular versus TC0
Kaveh
# Regular versus TC0

(Asked by: username_0 on 2016-01-02)

According to [the Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg),
$\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}$?

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, circuit-complexity, regular-language


---

## 2 answers

### Answer by username_4 on 2016-01-02. Score: 17 | Accepted answer

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"


---

### Answer by username_1 on 2016-01-02. Score: 15

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 username_4's answer).

> **Comments:**
> **username_2**: what is a syntactic monoid?  
> **username_1**: https://en.wikipedia.org/wiki/Syntactic_monoid  
> **username_1**: 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.  
> **username_1**: My favourite NC^1-complete regular expression is $((a|b)^3(ab^*a|b))^*$ (this is actually an encoding of S_5, as in username_4's answer).  
> **username_2**: So basically asking if there is a DFA not implementable in TC0 or in other words is graph reachability in TC0 right?  
> **username_3**: Would you mind indicating how $((a|b)^3(ab^*a|b))^*$ encodes $S_5$?  Thanks!  
> **username_4**: 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$.  
> **username_1**: @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.  
> **username_2**: @EmilJeřábek 1) If $REG$ is complete for $NC^1$ then because $TC^0$ is in $NC^1$ it seems $REG$ can count. Is it correct? 2) If $TC^0\neq NC^1$ is $ACC^0\neq TC^0$ unconditionally or is it possible $ACC^0=TC^0\neq NC^1$ is still allowed?  

---

