Referensi untuk bahasa Dyck adalah

12

Bahasa Dyck didefinisikan oleh tata bahasa $\mathsf{Dyck}(k)$ atas himpunan simbol . Bahasa secara intuitif Dyck adalah bahasa kurung seimbang dari yang berbeda. Sebagai contoh,

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$

Adalah di

tapi

([]) ()

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

D y c k (2)

$\mathsf{Dyck}(2)$

tidak.

([)]

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

Di koran

Algoritma Dinamis untuk Bahasa Dyck oleh Frandsen, Husfeldt, Miltersen, Rauhe, dan Skyum, 1995,

diklaim bahwa hasil berikut adalah cerita rakyat:

adalah -Lengkap bawah pengurangan. $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $\mathsf{AC}_0$

Apakah ada referensi yang diketahui untuk klaim di atas? Secara khusus, saya sedang mencari hasil yang menunjukkan setidaknya satu dari yang berikut:

adalah dalam untuk arbitrary . $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$
adalah -hard untuk sembarang. $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$

Makalah terdekat yang bisa saya temukan adalah

Bi-Lipschitz Bijection antara Boolean Cube dan Hamming Ball , oleh Benjamini, Cohen, dan Shinkar, 2013

yang mengarahkan saya ke makalah. Mengenali ruang dan terjemahan bahasa tanda kurung oleh Lynch yang membuktikan bahwa (yaitu, tanda kurung seimbang normal) ada di . $\mathsf{Dyck}(1)$ $\mathsf{TC_0}$

Setiap makalah terkait juga disambut. Terima kasih!

reference-request fl.formal-languages circuit-complexity ho.history-overview context-free Hsien-Chih Chang 張顯之
sumber

5

Lihat "Pada kompleksitas relatif beberapa bahasa di oleh Barrington, Corbett $\mathsf{NC}^1$

SamiD
sumber

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
sumber

Terima kasih. Apakah Anda tahu ada kertas yang berisi hasil di atas? (Tidak apa-apa jika kertasnya bukan yang asli / paling awal, saya mencoba untuk melacak kembali sejarah.)

Hsien-Chih Chang 張顯之

Hmmm ... untuk beberapa alasan saya berasumsi bahwa pengurangan serupa muncul di kertas Lynch itu ... Saya tidak tahu referensi lain untuk ini.

Igor Shinkar

Referensi untuk bahasa Dyck adalah

Jawaban: