Menentukan kemampuan mesin state min-heap (atau eksotik lainnya)

44

Lihat akhir tulisan ini untuk beberapa klarifikasi tentang definisi min-heap automata.

Orang dapat membayangkan menggunakan berbagai struktur data untuk menyimpan informasi untuk digunakan oleh mesin negara. Misalnya, push-down automata menyimpan informasi dalam tumpukan, dan mesin Turing menggunakan kaset. Mesin negara menggunakan antrian, dan yang menggunakan dua tumpukan atau kaset, telah terbukti setara dalam kekuatan untuk mesin Turing.

Bayangkan mesin min-heap. Ini berfungsi persis seperti otomat push-down, dengan pengecualian berikut:

  1. Alih-alih melihat hal terakhir yang Anda tambahkan ke heap, Anda hanya bisa melihat elemen terkecil (dengan urutan yang ditentukan berdasarkan per mesin) saat ini di heap.
  2. Alih-alih menghapus hal terakhir yang Anda tambahkan ke heap, Anda hanya bisa menghapus salah satu elemen terkecil (dengan urutan yang ditentukan berdasarkan per mesin) saat ini di heap.
  3. Alih-alih menambahkan elemen ke bagian atas heap, Anda hanya dapat menambahkan elemen ke heap, dengan posisinya ditentukan berdasarkan elemen lain di heap (dengan urutan yang ditentukan berdasarkan per mesin).

Mesin ini dapat menerima semua bahasa biasa, hanya dengan tidak menggunakan heap. Ia juga dapat menerima bahasa dengan menambahkan ke heap, dan menghapus 's dari tumpukan ketika membaca ' s. Itu dapat menerima berbagai bahasa bebas konteks lainnya. Namun, ia tidak dapat menerima, misalnya, (dinyatakan tanpa bukti). EDIT: atau bisakah? Saya tidak berpikir itu bisa, tapi saya pernah terkejut sebelumnya, dan saya yakin saya akan terus terkejut ketika asumsi saya untuk terus membuat saya menjadi ... well.{anbn{a,b}n0}aab{w{a,b}w=wR}

Bisakah ia menerima bahasa yang peka konteks atau lengkap Turing?

Secara lebih umum, penelitian apa, jika ada, yang telah ditempuh ke arah ini? Apa hasilnya di sana, jika ada? Saya juga tertarik pada varietas lain dari mesin negara eksotis, mungkin yang menggunakan struktur data lain untuk penyimpanan atau berbagai jenis pembatasan akses (misalnya, bagaimana LBA dibatasi TMs). Referensi dihargai. Saya minta maaf sebelumnya jika pertanyaan ini menunjukkan ketidaktahuan.


Definisi Resmi:

Saya memberikan beberapa definisi lebih rinci tentang min-heap automata di sini untuk menjelaskan diskusi lebih lanjut dalam pertanyaan yang merujuk materi ini.

Kami mendefinisikan otomat min-heap min-heap tipe-1 tipe-1 sebagai tupel 7 mana ...

(Q,q0,A,Σ,Γ,Z0,δ)
  1. Q adalah seperangkat status terbatas, tidak kosong;
  2. q0Q adalah kondisi awal;
  3. AQ adalah himpunan negara penerima;
  4. Σ adalah alfabet input terbatas, tidak kosong;
  5. γ Γ w ( γ ) N w ( γ 1 ) = w ( γ 2 )Γ adalah alfabet input terbatas, tidak kosong, di mana bobot simbol , , sedemikian rupa sehingga ;γΓw(γ)Nw(γ1)=w(γ2)γ1=γ2
  6. Z0Γ adalah simbol bottom-of-the-heap khusus;
  7. δ:Q×(Σ{ϵ})×(Γ{Z0})P(Q×Γ) adalah fungsi transisi.

Fungsi transisi bekerja dengan mengasumsikan tumpukan awalnya kosong yang hanya terdiri dari . Fungsi transisi dapat menambah tumpukan kumpulan sewenang-wenang (terbatas, tetapi mungkin kosong atau dengan pengulangan) elemen . Atau, fungsi transisi dapat menghapus instance elemen dengan bobot terendah dari semua elemen yang tersisa di heap (yaitu, elemen di atas heap). Fungsi transisi hanya dapat menggunakan instance simbol paling atas (yaitu, dengan berat minimum) dalam menentukan transisi yang diberikan.γ 1 , y 2 , . . . , γ kΓ γ w ( γ )Z0γ1,γ2,...,γkΓγw(γ)

Selanjutnya, tentukan automaton min-heap deterministik tipe-1 tipe menjadi automaton min-heap tipe-1 non-deterministik yang memenuhi properti berikut: untuk semua string sedemikian sehingga dan , .| x | = n σ Σ | δ n + 1 ( q 0 , x σ y , Z 0 ) | 1xσyΣ|x|=nσΣ|δn+1(q0,xσy,Z0)|1

Tentukan juga automaton min-heap tipe-2 nondeterministic yang persis sama dengan automaton min-heap tipe-1 nondeterministic, kecuali untuk perubahan berikut:

  1. γ Γ w ( γ ) N w ( γ 1 ) = w ( γ 2 ) γ 1 = γ 2Γ adalah alfabet input terbatas, tidak kosong, di mana bobot simbol , , sedemikian rupa sehingga tidak selalu menyiratkan ; dengan kata lain, berbagai simbol tumpukan dapat memiliki bobot yang sama.γΓw(γ)Nw(γ1)=w(γ2)γ1=γ2
  2. Ketika instance simbol heap yang berbeda dengan bobot yang sama ditambahkan ke heap, urutan relatifnya dipertahankan sesuai dengan pemesanan seperti-in-akhir, pertama-keluar (LIFO).

Terima kasih kepada Raphael karena menunjukkan definisi yang lebih alami ini, yang menangkap (dan memperluas) bahasa bebas konteks.


Beberapa hasil menunjukkan sejauh ini:

  1. Tipe-1 min-heap automata mengenali serangkaian bahasa yang bukan merupakan subset atau superset dari bahasa bebas konteks. [ 1 , 2 ]
  2. Automata min-heap tipe-2, menurut definisi mereka, mengenali serangkaian bahasa yang merupakan superset yang tepat dari bahasa bebas konteks, serta superset yang tepat dari bahasa yang diterima oleh automata automata tipe-1 min-heap.
  3. Bahasa yang diterima oleh tipe-1 min-heap automata tampaknya ditutup di bawah penyatuan, penggabungan, dan bintang Kleene, tetapi tidak di bawah komplemen [ 1 ], persimpangan, atau perbedaan;
  4. Bahasa yang diterima oleh min-heap automata nondeterministic tipe-1 nampaknya merupakan superset bahasa yang tepat yang diterima oleh min-heap automata deterministik min-heap tipe-1.

Mungkin ada beberapa hasil lain yang saya lewatkan. Lebih banyak hasil (mungkin) dalam perjalanan.


Pertanyaan Tindak Lanjut

  1. Penutupan di bawah pembalikan? -- Buka
  2. Penutupan di bawah komplementasi? -- Tidak!
  3. Apakah nondeterminisme meningkatkan kekuatan? -- Iya?
  4. Apakah untuk tipe-2? HALCSL-- Buka
  5. Apakah menambahkan tumpukan meningkatkan daya untuk tipe-1? - untuk (?)HAL1HAL2=HALkk>2
  6. Apakah menambahkan tumpukan meningkatkan daya untuk tipe-1? -- Buka
Patrick87
sumber
1
Pertanyaan yang bagus. Saya tergoda untuk menggali lemma pemompaan untuk automata ini.
Raphael
@ Raphael: Saya pikir Anda dapat menggunakan bukti (diperbarui) saya untuk lemma: bahasa apa pun yang Anda butuhkan untuk 'mengingat' lebih dari jumlah informasi linier dalam beberapa substring agar sesuai dengan substring berikutnya dengan benar tidak dapat diuraikan oleh min-heap automata. Saya tidak yakin apakah lemma gaya memompa yang sebenarnya mungkin terjadi - itu mungkin akan menjadi kasus khusus lemma saya juga.
Alex ten Brink
@AlextenBrink Karena kombinasi angka simbol tumpukan dapat digunakan untuk menyandikan hal-hal, saya tidak yakin cukup terikat linier.
Raphael

Jawaban:

25

Anda dapat mengenali bahasa kanonik non-konteks-bebas (tapi peka konteks) dengan jenis mesin status ini. Inti masalahnya adalah bahwa Anda menambahkan token ke tumpukan untuk setiap karakter, dan sementara parsing karakter, Anda menambahkan token 'lebih besar' ke tumpukan, sehingga mereka hanya berakhir di bagian bawah tumpukan ketika Anda telah diurai semua karakter.a b b{anbncn | n1}abb

Simbol heap adalah dan , di mana . Kita mengkonsumsi semua simbol pada input dan menambahkan simbol untuk heap. Jika kita menghadapi , kita beralih strategi: untuk setiap kita temui kemudian kita menghapus dari tumpukan dan menambahkan ke tumpukan. Ketika kita menghadapi kita harus kehabisan s untuk menghapus, dan kemudian untuk setiap di masukan tersisa kami menghapus dari tumpukan. Jika tumpukan kosong di akhir, string dalam bahasa. Jelas, kami menolak jika terjadi kesalahan.b a < b a a b b a b c a c baba<baabbabcacb

Memperbarui:

Bahasa tidak dapat dikenali oleh min-heap automata. Misalkan kita memang memiliki robot min-heap yang dapat mengenali . Kita melihat 'status' tempat otomat berada setelah membaca (bagian pertama dari input, jadi adalah yang berikutnya). Satu-satunya negara yang kita miliki adalah isi dari tumpukan dan negara tertentu otomat itu dalam. Ini berarti bahwa setelah mengakui , ini 'negara' kebutuhan untuk menahan informasi yang cukup untuk mencocokkan .E P A L w w R w w REPAL={wwR|w{a,b}}EPALwwRwwR

Secara khusus, dalam rangka untuk melakukan hal ini, harus ada mungkin berbeda 'negara (di mana ), karena ada mungkin kata-kata yang terdiri dari dan karakter. Karena hanya ada sejumlah negara terbatas dan hanya sejumlah karakter heap, ini menyiratkan bahwa ada beberapa kata yang heap berisi angka eksponensial dari beberapa karakter heap, katakanlah .2nn=|w|2nabwx

Kami pertama-tama membuktikan teorema untuk min-heap automata deterministik, dan kemudian memperluas bukti ini ke min-heap automata non-deterministik. Secara khusus, automata deterministik yang mengenali beberapa bahasa tidak akan menempatkan dirinya dalam loop tak terbatas, yang merupakan properti yang berguna.

Kami akan membuktikan bahwa heap hanya dapat berisi paling banyak sejumlah token heap yang linier dalam jumlah karakter yang dibaca dari input. Ini dengan segera bahwa muncul beberapa kali secara eksponensial pada heap, yang melengkapi bukti bahwa tidak dapat dikenali oleh min-heap automata.xEPAL

Karena kita hanya memiliki sejumlah negara terbatas dalam otomat kita dan karena otomat deterministik tidak akan menempatkan dirinya dalam loop tak terbatas, saat membaca sinyal input, ia akan menambah paling banyak jumlah karakter heap konstan ke heap. Demikian pula, pada mengkonsumsi beberapa simbol tumpukan , itu hanya menambah paling sejumlah konstan karakter tumpukan yang ketat lebih besar dari dan hanya dapat menurunkan jumlah simbol pada stack (jika kita mendapatkan loop tak terbatas).yyy

Karena itu, mengonsumsi simbol tumpukan dapat menyebabkan penumpukan simbol tumpukan yang lebih besar (besar), tetapi karena hanya ada sejumlah jenis simbol tumpukan yang konstan, ini hanya angka konstan yang tidak bergantung pada . Ini menyiratkan bahwa jumlah simbol tumpukan paling banyak beberapa kali (besar) konstan jumlah simbol input yang dibaca sejauh ini. Ini melengkapi bukti untuk kasus deterministik.n

Dalam kasus non-deterministik, buktinya serupa, tetapi sedikit lebih rumit: daripada menambahkan paling banyak beberapa token heap ke heap, itu menambah beberapa token heap toge ke heap. Namun, poin pentingnya adalah bahwa angka ini tidak bergantung pada . Secara khusus, jika kita dapat secara non-deterministik mendapatkan simbol tumpukan yang tepat pada heap setelah mengenali (tepat untuk mengenali ), kita juga dapat secara non-deterministik memilih simbol tumpukan yang cocok dengan kata lain , dan dengan demikian mengenali , dengan demikian bertentangan bahwa otomat min-heap mengenali persis .nwwRwwwREPAL

Pembaruan 3: Saya akan membuat argumen terakhir (tentang non-determinisme) ketat. Dengan argumen di atas, harus ada sekumpulan kata tak terbatassedemikian rupa sehingga untuk setiap, setelah mengenali, heap berisielemen( perhatikan bahwa kita dapat berbicara tentangkarena kita memiliki serangkaian kata yang tak terbatas). Karena kita tidak bisa mendapatkan banyak elemen pada heap melalui cara deterministik, kita harus memiliki beberapa bentuk loop di mana pertama-tama kita secara non-deterministik memilih untuk menambahkan lebih banyak elemen ke heap (tanpa mengkonsumsi input), dan kemudian memilih untuk keluar dari ini loop, dan kita harus melewati loop inikali.W{a,b}wWwω(|w|)O(f(|w|))ω(1)

Ambil himpunan semua loop seperti yang digunakan oleh . Karena hanya ada menyatakan, ukuran himpunan ini adalah , dan himpunan semua himpunan bagiannya juga . Sekarang perhatikan bahwa bagian 'deterministik' dari jalur eksekusi hanya dapat berkontribusi pada dari token, yang berarti bahwa banyak jumlah eksponensial dari kata-kata yang berbeda harus memiliki jalur eksekusi yang bagian-bagian 'deterministik' berkontribusi sama. token ke tumpukan. Secara khusus, satu-satunya cara untuk mendapatkan lebih banyak token adalah dengan mengambil loop yang kami identifikasi di atas.WO(1)O(1)O(1)O(|w|)

Menggabungkan pengamatan ini, ini berarti bahwa harus ada dua kata berbeda dalam , dan katakan, yang bagian 'deterministik' dari jalur eksekusi berkontribusi token yang sama ke heap, dan yang dibedakan dengan mengambil beberapa bagian dari loop di atas beberapa kali berbeda, tetapi yang menggunakan subset loop yang sama (ingat hanya ada dari loop ini).Ww1w2O(1)

Kami sekarang dapat menunjukkan bahwa juga dapat dikenali oleh min-heap automaton: kami mengikuti jalur eksekusi untuk seperti di atas, tetapi kami melewati loop dengan jumlah yang sama dengan jalur eksekusi untuk melewatinya. Ini mengisi min-heap dengan token sehingga diterima sebagai suffix, sehingga melengkapi buktinya.w1w2w1w2w2

Pembaruan 2:

Baru terpikir oleh saya bahwa di atas berarti bahwa kita dapat mensimulasikan robot min-heap deterministik hanya menggunakan ruang logaritmik: kita menyimpan penghitung untuk setiap jenis karakter dalam min-heap. Seperti yang ditunjukkan di atas, penghitung ini paling banyak akan menjadi , dan karenanya dapat disimpan hanya menggunakan ruang (karena hanya ada jumlah konstan penghitung ini). Ini memberi kita:O(n)O(logn)

DHALL

HALNL

di mana adalah sekumpulan bahasa yang dikenali oleh beberapa otomat min-heap deterministik.DHAL

Alex ten Brink
sumber
1
+1 untuk wawasan yang bagus, sepertinya Anda telah memahami maksud saya sepenuhnya. Apakah saya benar dalam penilaian saya bahwa mesin seperti itu tidak dapat mengenali palindrom? Karena urutan simbol yang ditambahkan tidak dipertahankan, sepertinya tidak mungkin.
Patrick87
@ Patrick87: Saya sedang memikirkan masalah itu sekarang :)
Alex ten Brink
@Raphael Pengamatan yang sangat keren tentang mesin Turing dengan kendala sumber daya logaritmik, kalian berdua telah melakukan pekerjaan luar biasa dalam menyelidiki automata ini. Anda tahu, saya semacam hanya membuang robot min-heap sebagai semacam contoh hal yang saya minati, tetapi sepertinya diterima dengan baik. Apa pertanyaan lain yang dapat dijawab tentang automata tersebut? Apakah DHAL = HAL? Apa properti penutupan HAL? Apakah eksplorasi lebih lanjut bermanfaat, dan jika demikian, haruskah mereka tetap di sini, atau diajukan ke pertanyaan baru? Sekali lagi terima kasih atas wawasannya yang luar biasa.
Patrick87
1
@ Raphael: Saya sudah membuat bagian itu sepenuhnya keras. Anda benar bahwa harus cukup besar - saya mengulas beberapa detail kiri dan kanan. n
Alex ten Brink
1
@ Raphael: Memang benar. , jadi oleh teorema hierarki ruang dan beberapa inklusi. CSL=NLINSPACEDHALCSL
Alex ten Brink
19

Inilah yang kami (yakini) ketahui:

  • HALCFL (tipe-1, tipe-2)
  • CFLHAL (tipe-1)
  • CFLHAL (tipe-2, menurut definisi)
  • CSLHAL (tipe-1, tipe-2)

Lihat detail dan beberapa catatan lainnya di bawah ini.


HALCFL

Bagian jawaban ini terkait dengan tipe-1 dan tipe-2.

Automaton min-heap (HA) dengan alfabet tumpukan yang terbatas, benar-benar dipesan menerima .L={anbncnnN}CSLCFL

Asumsi: Mirip dengan PDA, fungsi transisi kita mengkonsumsi simbol heap paling atas dan menulis kembali sejumlah simbol heap. Tumpukan awalnya berisi simbol dibedakan yang lebih besar dari semua simbol tumpukan lainnya.$

Biarkan otomat min-heap denganA=(Q,ΣI,ΣH,,q0,QF)

  • Q={q0,q1,q2,qf} set negara
  • ΣI={a,b,c} alfabet input.
  • ΣH=a,b,$ alfabet tumpukan dengan memesan .a<b<$
  • QF={qf}
  •  (Q×ΣI×ΣH)×(Q×ΣH) dengan
    • (q0,a,σ)(q0,aσ) untuk semuaσΣH
    • (q0,b,a)(q1,b)
    • (q1,b,a)(q1,b)
    • (q1,c,b)(q2,ε)
    • (q2,c,b)(q2,ε)
    • (q2,c,$)(qf,ε)

Automaton menulis satu ke heap untuk setiap di input. Ketika terjadi, mengkonsumsi banyak karena ada telah , menulis ke tumpukan untuk setiap ditemukan . Ini tidak mengganggu penghitungan karena tumpukan dengan mudah menjaga di atas. Hanya setelah semua diambil dari heap diterima; hanya setelah sebanyak sebanyak (dan selanjutnya sebagai ) ditemukan, apakah menerima dengan tumpukan kosong dan keadaan akhir.aabbabbaaccbaA

Oleh karena itu, .L(A)=L


CFLHAL

Bagian jawaban ini hanya berhubungan dengan tipe-1.

Pertimbangkan himpunan palindrom bahkan dan menganggap ada HA dengan .EPAL={wwRw{a,b}}AL(A)=L

Dugaan: kami menemukan dengan dansedemikian rupa sehingga berada dalam keadaan yang sama dan memiliki konten tumpukan yang sama setelah masing-masing membaca dan . Karena menerima dan , maka A juga menerima (dan ), yang merupakan kontradiksi dengan .w1,w2{a,b}w1w2|w1|=|w2|Aw1w2Aw1w1Rw2w2Rw1w2REPALw2w1RL(A)=EPAL


CSLHAL

Bagian jawaban ini terkait dengan tipe-1 dan tipe-2.

Alasan yang sama yang kami gunakan pada (untuk tipe-1) dapat digunakan untuk menunjukkan bahwa bahasa konteks-sensitif tidak dalam . { w w w { a , b } } H A LEPAL{www{a,b}}HAL


HAL?CSL

Ini masih terbuka untuk tipe-1 dan tipe-2.


Faktoroids Lebih Lanjut

HA tampaknya ortogonal ke bagian dari bahasa konteks-agak ringan diterima oleh Embedded Pushdown Automata : Sementara HA dapat mensimulasikan sejumlah tumpukan tumpukan yang ditumpuk, mereka tidak dapat mensimulasikan banyak sembarang (seperti yang dapat dilakukan EPA). Namun, HA dapat mengakses simbol tumpukan paling atas saat ini tidak di atas (yang EPA tidak bisa).

Raphael
sumber
+1, respons luar biasa. Pada dasarnya setara dengan metode Brink, kan? Meski begitu, ketelitian dan ketelitiannya luar biasa. Sudahkah Anda memikirkan apakah mesin tersebut dapat menerima semua CFL? Tampaknya mustahil, karena informasi pesanan hilang oleh tumpukan ...
Patrick87
Itu ide yang sama dengan Alex, ya. Senang Anda bisa mendapatkan sesuatu darinya. Saya menambahkan ide untuk arah lain tetapi ada kesenjangan (besar?). Perlu memikirkannya dengan kepala yang jelas besok dan mungkin menembak beberapa rekan.
Raphael
Saya merasa saya harus memasukkan bukti kebenaran untuk mendapatkan kredit ekstra untuk kekakuan. ;) Seharusnya tidak terlalu sulit dengan induksi lebih dari , kurasa. n
Raphael
Garis besar bukti yang Anda label sebagai dugaan adalah apa yang ada dalam pikiran saya, dan saya merasa cukup meyakinkan ... juga, dan ini adalah titik teknis minor, saya pikir Anda menggunakan bahasa palindrom yang panjangnya merata, tidak semua palindrom ... meskipun buktinya tentu bekerja dengan baik (perhatikan bahwa itu juga bekerja untuk palindrom sederhana, sehingga HAL bahkan tidak sekuat DPDA, hasil lain).
Patrick87
@ Patrick87 Masalahnya adalah bahwa mungkin ada lebih banyak konfigurasi yang mungkin diberikan HA setelah membaca simbol daripada kata-kata, khususnya jika kita mengizinkan -transisi yang meletakkan simbol pada heap. εnε
Raphael