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

12

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

S \to S S | (_{1} S)_{1} | \dots | (_{k} S)_{k} | ϵ

$S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon$

{(_{1}, \dots, (_{k},)_{1}, \dots,)_{k}}

$\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$

k

$k$

jest w

ale

([]) ()

$(\,[\,]\,)\,(\,)$

D y c k (2)

$\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 -Complete pod 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 dla dowolnego . $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$
jest -hard arbitralne . $\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!

— Hsien-Chih Chang 張顯之
źródło

5

$\mathsf{NC}^1$

— SamiD
źródło

6

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

— Igor Shinkar
źródło

Dzięki. Czy znasz jakiś artykuł, który zawiera powyższy wynik? (Jest w porządku, jeśli papier nie jest oryginalny / najwcześniejszy, staram się prześledzić historię.)

— Hsien-Chih Chang 張顯之

Hmmm ... z jakiegoś powodu założyłem, że podobna redukcja pojawiła się w tym artykule Lyncha ... Nie znam na to innych odniesień.

— Igor Shinkar