Odniesienie do języków Dyck, które są kompletne dla

Języki Dyck definiuje następująca gramatyka S → S $\mathsf{Dyck}(k)$ nad zbiorem symboli { ( 1 , … , ( k , ) 1 , … , ) k } . Języki intuicyjnie Dyck są językami zbilansowanych nawiasów k innego rodzaju. Na przykład

$$S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon$$ $\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$$k$ jest w D y c k ( 2 ), ale$(\,[\,]\,)\,(\,)$$\mathsf{Dyck}(2)$ nie jest.$(\,[\,)\,]$

Na papierze

Dynamiczne algorytmy dla języków Dyck autorstwa Frandsena, Husfeldta, Miltersena, Rauhe i Skyuma, 1995,

twierdzi się, że następujący wynik to folklor:

jest T C 0 -Complete pod A C 0 redukcji.$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$\mathsf{AC}_0$

Czy znane jest odniesienie do powyższego roszczenia? W szczególności szukam wyników, które pokazują co najmniej jedną z następujących czynności:

• jest w T C 0 dla dowolnego k .$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$k$
• jest T C 0 -hard arbitralne k .$\mathsf{Dyck}(k)$$\mathsf{TC}_0$$k$

---

Najbliższy papier, jaki mogę znaleźć, to

Bi-Lipschitz Bijection between Boolean Cube and the Hamming Ball , autor: Benjamini, Cohen i Shinkar, 2013

$\mathsf{Dyck}(1)$$\mathsf{TC_0}$

Wszelkie powiązane dokumenty są również mile widziane. Dzięki!

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