Theoretical Computer Science

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

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!


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