Référence pour les langues Dyck étant complète en

Les langages Dyck sont définis par la grammaire suivante S → S $\mathsf{Dyck}(k)$ sur l'ensemble des symboles { ( 1 , … , ( k , ) 1 , … , ) k } . Langues Intuitivement Dyck sont les langues de parenthèses équilibré de k genre différent. Par exemple,

$$S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon$$ $\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$$k$ est en D y c k ( 2 ) mais$(\,[\,]\,)\,(\,)$$\mathsf{Dyck}(2)$ ne l'est pas.$(\,[\,)\,]$

Dans le journal

Algorithmes dynamiques pour les langues Dyck par Frandsen, Husfeldt, Miltersen, Rauhe et Skyum, 1995,

on prétend que le résultat suivant est le folklore:

est T C 0 - complet sous lesréductions A C 0 .$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$\mathsf{AC}_0$

Y a-t-il une référence connue pour la revendication ci-dessus? En particulier, je recherche des résultats montrant au moins l'un des éléments suivants:

• est dans T C 0 pour k arbitraire.$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$k$
• est T C 0 -hard pour arbitraire k .$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$k$

---

Le document le plus proche que je peux trouver est

Bi-Lipschitz Bijection entre le cube booléen et la balle de Hamming , par Benjamini, Cohen et Shinkar, 2013

qui me redirige vers la reconnaissance de l'espace des journaux et la traduction des langages de parenthèses par Lynch qui a prouvé que (c'est-à-dire les parenthèses équilibrées normales) est dans T C 0 .$\mathsf{Dyck}(1)$$\mathsf{TC_0}$

Tous les documents connexes sont également les bienvenus. Merci!

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