Dapatkah multipebble automata menentukan semua bahasa yang peka konteks-deterministik?

MPA (multipebble automaton) adalah 2DFA (otomat hingga hingga deterministik dua arah) yang dapat menggunakan jumlah kerikil yang sewenang-wenang (sebenarnya paling banyak kerikil pada input yang diberikan - input ditulis pada kaset di antara dua ujung -Penanda sebagai ). Selama perhitungan, MPA dapat mendeteksi apakah simbol di bawah kepala memiliki kerikil, dan kemudian dapat menempatkan kerikil (menghapus kerikil) jika tidak ada kerikil (kerikil). $|w|+2$ $w$ $\# w \#$

$h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k$ adalah homomorfisme, di mana adalah simbol dan . $\sigma$ $k>0$

Untuk bahasa sensitif konteks yang deterministik tidak sulit untuk menunjukkan bahwa ada sedemikian rupa sehingga dapat dikenali oleh MPA. Jadi, secara longgar, kita bisa mengatakan itu $\mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right),$ $k>0~$ $h_k( \mathtt{L} )$

"masalah" apa pun yang dapat diuraikan oleh DTM linear-space (mesin Turing deterministik) dapat diuraikan oleh MPA.

Apakah benar juga untuk bahasa apa pun di ? Dapatkah KPL menentukan semua bahasa yang sensitif terhadap konteks deterministik? $\mathsf{DSPACE(n)}$

$|w|$ adalah panjang . $w$

$w_i$ adalah dari , di mana. $i^{th}$ $w$ $1 \leq i \leq |w|$

$h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace$ .

cc.complexity-theory reference-request automata-theory space-bounded Abuzer Yakaryilmaz
sumber

pertanyaan menarik; berniat memposting beberapa referensi yang berhubungan dengan longgar yang mungkin relevan jika tidak ada orang lain yang memberikan sesuatu yang lebih baik / lebih dekat. sebuah pertanyaan. CSL yang ada di DSpace (n) tidak harus sama dengan semua DTM linear-space, kan? sebenarnya itu pertanyaan terbuka kan? atau terkait erat dengan satu? karena CSL terbukti sama dengan NSpace (n) dan terbuka jika NSpace (n) == DSpace (n).

vzn

@ vzn: CSL yang ada di DSPACE (n) disebut CSL deterministik, dan mereka membentuk persis DSPACE (n).

Abuzer Yakaryilmaz

baik. ref yang ada dalam pikiran saya sebagai "mungkin terkait" adalah argumen pebbling yang digunakan untuk menyerang DTime (n ^ k) =? Ntime (n ^ k) pertanyaan misalnya hasil terbaru dari bangunan Santhanam pada hasil PPST. masalah lain yang menurut saya berhubungan adalah masalah kompresi urutan run TM

vzn

bisakah Anda menjelaskan beberapa pertanyaan? tidakkah Anda hanya menegaskan dalam teks yang disorot bahwa KKL dapat memutuskan semua CSL deterministik? mis. adakah cara untuk mengulangi pertanyaan Anda dengan istilah h_k (L)?

vzn

Teorema adalah bahwa jika adalah DCSL, ada beberapa sedemikian rupa sehingga dapat dihitung oleh MPA. Pertanyaannya adalah, bisakah kita mengambil ?

σ

$\sigma$

k

$k$

h_{k} (σ)

$h_k(\sigma)$

k = 1

$k=1$

Ben Standeven

Jawaban:

Mungkin Anda dapat membangun bahasa di DPSACE (n) yang tidak dapat dikenali oleh MPA dengan menggunakan argumen diagonalisasi (mungkin idenya mirip dengan yang ada di jawaban Ben, tapi saya tidak menggali ke dalamnya): $k=1$

Misalkan lebih dari alfabet Anda menyandikan MPA menggunakan daftar transisi: $\Sigma = \{0,1\}$

$s,a,p \rightarrow s',p',L|R;...\#$

di mana adalah keadaan saat ini, adalah simbol saat ini, adalah status kerikil, adalah keadaan baru, adalah keadaan kerikil baru, adalah arah gerakan, adalah tanda akhir). $s$ $a$ $p$ $s'$ $p'$ $L|R$ $\#$

Mesin Turing pada input dapat memeriksa apakah ini merupakan deskripsi yang dan mensimulasikannya pada input untuk langkah menggunakan sel, meregangkan input dengan cara ini: $M$ $x$ $MPA_x$ $x$ $4^{|x|}$ $6|x|+\log|x|$

 MPA description # MPA tape # curr_state # counter #

Dimana:

Deskripsi MPA adalah string input asli (memiliki panjang ); $x$ $|x|$
Tape MPA adalah representasi tape MPA: untuk setiap sel kita dapat menggunakan 3 bit untuk menyimpan flag head, flag kerikil, dan konten tape (tetap) (memiliki panjang ); $3|x|$
curr_state menyimpan status KKL saat ini (memiliki panjang ); $\log |x|$
penghitung adalah penghitung langkah simulasi yang diperbarui setelah setiap langkah simulasi (memiliki panjang ). $2|x|$

Jika berhenti dalam langkah maka TM menghasilkan sebaliknya (jika tidak menghentikan menghasilkan 0). $MPA_x$ $4^{|x|}$ $M$ $M$

$x > x_0$ $4^{|x|}$ $2^{|x|+2} |x| \log |x|$ $MPA_x$ $MPA_x$ $4^{|x|}$

$MPA_y$ $L$ $M$ $MPA_{y'}$ $y'>x_0$

$MPA_{y'}(y') = 1 - M(y') = 1 - MPA_{y'}(y')$

Marzio De Biasi
sumber

Ya, itulah argumen yang ada dalam pikiran saya.

Ben Standeven

$\log(N(|k|+2))+|k|+2$

Karena bahasa ini dapat dipilih dalam ruang linear, bahasa ini juga dapat dinyatakan sebagai DCSL.

Ben Standeven
sumber

Mungkin saya kehilangan beberapa poin sederhana tetapi saya tidak bisa mendapatkan bagaimana contoh balasan Anda bekerja. Bisakah Anda lebih deskriptif tentang cara kerja argumen Anda? Terima kasih!!!

Abuzer Yakaryilmaz