LogDCFL-menyelesaikan masalah

LogCFL adalah himpunan semua bahasa yang logspace direduksi menjadi bahasa bebas konteks. Demikian pula, LogDCFL adalah himpunan semua bahasa yang logspace direduksi menjadi bahasa bebas konteks deterministik. Lihat artikel wikipedia ini untuk beberapa masalah lengkap LogCFL. Ada beberapa masalah lengkap lengkap yang menarik dari LogCFL. Saya tidak dapat menemukan masalah lengkap LogDCFL alami. Beri nama setiap masalah yang diselesaikan dengan lengkap LogDCFL.

cc.complexity-theory complexity-classes Siwa Kintali
sumber

Karena penasaran, bolehkah saya bertanya mengapa Anda tertarik dengan LogDCFL?

Michaël Cadilhac

Saya tertarik pada perhitungan ruang-terbatas secara umum dan mencoba memahami LogDCFL.

Shiva Kintali

Jawaban:

Bahasa berikut adalah sedikit perubahan dari yang lengkap lengkap LogCFL sehingga LogDCFL selesai. Buktinya dapat ditemukan di Sudborough's On the Tape Complexity of Deterministic Context Languages.

Biarkan dan . Bahasa berikut di atas adalah lengkap-LogDCFL. terdiri dari kata-kata mana sedemikian rupa sehingga terdapat dengan atau untuk semua dan benar secara parenthetically benar. $\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$

w_{0} [(_{1} l_{1} | (_{2} r_{1}] ... [(_{1} l_{n} | (_{2} r_{n}]

$w_0\left[(_1l_1|(_2r_1\right]\ldots\left[(_1l_n|(_2r_n\right]$

w_{0}, l_{i}, r_{i} \in Σ^{*}

$w_0, l_i, r_i \in \Sigma^*$

w_{1}, \dots, w_{n}

$w_1, \ldots, w_n$

w_{i} = (_{1} l_{i}

$w_i = (_1l_i$

w_{i} = (_{2} r_{i}

$w_i = (_2r_i$

i \geq 1

$i \geq 1$

w_{0} w_{1} \dots w_{n}

$w_0w_1\ldots w_n$

Michaël Cadilhac
sumber