12
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 14 '14 at 16:47
  • $\begingroup$ 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. $\endgroup$ – Igor Shinkar Mar 16 '14 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.