Reference for Dyck languages being $\mathsf{TC}_0$-complete

Question

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 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, by Benjamini, Cohen, and Shinkar, 2013

which redirects me to the paper Log space recognition and translation of parenthesis languages 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!

Answer 1

See "On the relative complexity of some languages in $\mathsf{NC}^1$ by Barrington,Corbett

Answer 2

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