<p>See "On the relative complexity of some languages in $\mathsf{NC}^1$ by <a href="http://dx.doi.org/10.1016/0020-0190%2889%2990052-5">Barrington,Corbett</a></p>

CC BY-SA 3.0
2014-04-27T11:45:44.300Z
2014-04-27T11:45:44.300Z
SamiD
<p>Here is an $AC_0$ reduction from $\rm Majority$ to $Dyck(1)$.
(This implies that $\rm Majority$ is $AC_0$ reducible to $Dyck(k)$ for all $k \geq 1$.)
In order to do it, we construct a poly-size
constant depth circuit whose gates are $AND$, $OR$, $NOT$ and $Dyck(1)$.</p>

<hr>

<ul>
<li>Given an instance $x \in \{0,1\}^n$ of $\rm Majority$ do</li>
<li>Compute $y \in \{0,1\}^{2n}$ by replacing each $0$ with $(($ and each $1$ with $()$.</li>
<li>Now for each $i = 1,\dots, n/2$ let $z_i$ be the string obtained by concatenating $y$ with $2i$-many closing parentheses, i.e. $z_i = y \circ )^{2i}$.</li>
<li>If $z_i \in Dyck(1)$ for some $i = 1,\dots, n/2$ then ACCEPT.
Otherwise, REJECT.</li>
</ul>

<hr>

<p>This can be clearly done with a constant depth circuit. (Computing $z_i$ can be done in depth 1, and computing the last step is done using an $OR$ gate.)</p>

<p>It is also easy to see that this circuit indeed computes $\rm Majority$ because $z_i \in Dyck(1)$ if and only if ${\rm weight}(x) = n - i$.</p>

CC BY-SA 3.0
2014-03-14T16:47:58.703Z
Thanks.  Do you know any paper that contains the result above?  (It is ok if the paper is not the original/earliest one, I am trying to trace back the history.)
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-03-16T08:31:08.000Z
Hmmm... for some reason I assumed that a similar reduction appeared in that paper of Lynch... I don't know any other reference for this.
Igor Shinkar
CC BY-SA 3.0
2014-03-14T07:55:31.390Z
2014-03-14T13:41:16.307Z
2014-03-14T13:41:16.307Z
Igor Shinkar
<p>Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar
$$
S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon
$$
over the set of symbols $\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$.  Intuitively Dyck languages are the languages of balanced parentheses of $k$ different kind.  For example, $(\,[\,]\,)\,(\,)$ is in $\mathsf{Dyck}(2)$ but $(\,[\,)\,]$ is not.</p>

<p>In the paper </p>

<blockquote>
  <p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.5560&amp;rep=rep1&amp;type=pdf">Dynamic Algorithms for the Dyck Languages</a> by Frandsen, Husfeldt, Miltersen, Rauhe, and Skyum, 1995,</p>
</blockquote>

<p>it is claimed that the following result is folklore:</p>

<blockquote>
  <p>$\mathsf{Dyck}(k)$ is $\mathsf{TC}_0$-complete under $\mathsf{AC}_0$ reductions.</p>
</blockquote>

<p>Is there any reference known for the above claim?  In particular, I'm looking for any results that shows at least one of the following:</p>

<ul>
<li>$\mathsf{Dyck}(k)$ is in $\mathsf{TC}_0$ for arbitrary $k$.</li>
<li>$\mathsf{Dyck}(k)$ is $\mathsf{TC}_0$-hard for arbitrary $k$.</li>
</ul>

<hr>

<p>The closest paper I can find is</p>

<blockquote>
  <p><a href="http://arxiv.org/abs/1310.2017">Bi-Lipschitz Bijection between the Boolean Cube
  and the Hamming Ball</a>, by Benjamini, Cohen, and Shinkar, 2013</p>
</blockquote>

<p>which redirects me to the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.7200&amp;rep=rep1&amp;type=pdf">Log space recognition and translation of parenthesis languages</a> by Lynch who proved that $\mathsf{Dyck}(1)$ (that is, normal balanced parentheses) is in $\mathsf{TC_0}$.</p>

<p>Any related papers are welcomed as well.  Thanks!</p>

<reference-request><fl.formal-languages><circuit-complexity><ho.history-overview><context-free>
Reference for Dyck languages being $\mathsf{TC}_0$-complete
Hsien-Chih Chang 張顯之
# Reference for Dyck languages being $\mathsf{TC}_0$-complete

(Asked by: username_0 on 2014-03-14)

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar
$$
S \rightarrow SS \,|\, (\_1 S )\_1 \,|\, \ldots \,|\, (\_k S )\_k \,|\, \epsilon
$$
over the set of symbols $\{(\_1,\ldots,(\_k,)\_1,\ldots,)\_k\}$. Intuitively Dyck languages are the languages of balanced parentheses of $k$ different kind. For example, $(\,[\,]\,)\,(\,)$ is in $\mathsf{Dyck}(2)$ but $(\,[\,)\,]$ is not.

In the paper

> [Dynamic Algorithms for the Dyck Languages](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.5560&rep=rep1&type=pdf) by Frandsen, Husfeldt, Miltersen, Rauhe, and Skyum, 1995,

it is claimed that the following result is folklore:

> $\mathsf{Dyck}(k)$ is $\mathsf{TC}\_0$-complete under $\mathsf{AC}\_0$ reductions.

Is there any reference known for the above claim? In particular, I'm looking for any results that shows at least one of the following:

* $\mathsf{Dyck}(k)$ is in $\mathsf{TC}\_0$ for arbitrary $k$.
* $\mathsf{Dyck}(k)$ is $\mathsf{TC}\_0$-hard for arbitrary $k$.

---

The closest paper I can find is

> [Bi-Lipschitz Bijection between the Boolean Cube
> and the Hamming Ball](http://arxiv.org/abs/1310.2017), by Benjamini, Cohen, and Shinkar, 2013

which redirects me to the paper [Log space recognition and translation of parenthesis languages](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.7200&rep=rep1&type=pdf) by Lynch who proved that $\mathsf{Dyck}(1)$ (that is, normal balanced parentheses) is in $\mathsf{TC\_0}$.

Any related papers are welcomed as well. Thanks!

**Tags:** reference-request, fl.formal-languages, circuit-complexity, ho.history-overview, context-free

---

## 2 answers

### Answer by username_1 on 2014-04-27. Score: 5 | Accepted answer

See "On the relative complexity of some languages in $\mathsf{NC}^1$ by [Barrington,Corbett](http://dx.doi.org/10.1016/0020-0190%2889%2990052-5)


---

### Answer by username_2 on 2014-03-14. Score: 7

Here is an $AC\_0$ reduction from $\rm Majority$ to $Dyck(1)$.
(This implies that $\rm Majority$ is $AC\_0$ reducible to $Dyck(k)$ for all $k \geq 1$.)
In order to do it, we construct a poly-size
constant depth circuit whose gates are $AND$, $OR$, $NOT$ and $Dyck(1)$.

---

* Given an instance $x \in \{0,1\}^n$ of $\rm Majority$ do
* Compute $y \in \{0,1\}^{2n}$ by replacing each $0$ with $(($ and each $1$ with $()$.
* Now for each $i = 1,\dots, n/2$ let $z\_i$ be the string obtained by concatenating $y$ with $2i$-many closing parentheses, i.e. $z\_i = y \circ )^{2i}$.
* If $z\_i \in Dyck(1)$ for some $i = 1,\dots, n/2$ then ACCEPT.
  Otherwise, REJECT.

---

This can be clearly done with a constant depth circuit. (Computing $z\_i$ can be done in depth 1, and computing the last step is done using an $OR$ gate.)

It is also easy to see that this circuit indeed computes $\rm Majority$ because $z\_i \in Dyck(1)$ if and only if ${\rm weight}(x) = n - i$.

> **Comments:**
> **username_0**: Thanks.  Do you know any paper that contains the result above?  (It is ok if the paper is not the original/earliest one, I am trying to trace back the history.)  
> **username_2**: Hmmm... for some reason I assumed that a similar reduction appeared in that paper of Lynch... I don't know any other reference for this.  

---

