Referência para as línguas Dyck sendo

Idiomas dyck são definidos pela seguinte gramática S → S $\mathsf{Dyck}(k)$ sobre o conjunto de símbolos { ( 1 , … , ( k , ) 1 , … , ) k } . Linguagens intuitivamente dyck são as linguagens de parênteses balanceados de k tipos diferentes. Por exemplo,

$$S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon$$ $\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$$k$ está em D y c k ( 2 ) mas$(\,[\,]\,)\,(\,)$$\mathsf{Dyck}(2)$ não é.$(\,[\,)\,]$

No papel

Algoritmos dinâmicos para os idiomas dyck de Frandsen, Husfeldt, Miltersen, Rauhe e Skyum, 1995,

alega-se que o seguinte resultado é folclore:

é T C 0 completo sobreduções de A C 0 .$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$\mathsf{AC}_0$

Existe alguma referência conhecida para a reivindicação acima? Em particular, estou procurando resultados que mostrem pelo menos um dos seguintes:

• está em T C 0 para k arbitrário.$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$k$
• é T C 0 -hard para k arbitrário.$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$k$

---

O artigo mais próximo que encontro é

Bi-Lipschitz Bijection entre o cubo booleano e a bola de Hamming , por Benjamini, Cohen e Shinkar, 2013

que me redireciona para o artigo Reconhecimento do espaço de log e tradução de idiomas entre parênteses por Lynch, que provou que (ou seja, parênteses normais balanceados) está em T C 0 .$\mathsf{Dyck}(1)$$\mathsf{TC_0}$

Quaisquer documentos relacionados também são bem-vindos. Obrigado!

$\mathsf{NC}^1$

$AC_0$$\rm Majority$$Dyck(1)$$\rm Majority$$AC_0$$Dyck(k)$$k \geq 1$$AND$$OR$$NOT$$Dyck(1)$

---

• $x \in \{0,1\}^n$$\rm Majority$
• $y \in \{0,1\}^{2n}$$0$$(($$1$$()$
• $i = 1,\dots, n/2$$z_i$$y$$2i$$z_i = y \circ )^{2i}$
• $z_i \in Dyck(1)$$i = 1,\dots, n/2$

---

$z_i$$OR$

$\rm Majority$$z_i \in Dyck(1)$${\rm weight}(x) = n - i$