Kekuatan komputasi automata min-heap deterministic versus nondeterministic

Ini adalah pertanyaan lanjutan dari pertanyaan ini .

Dalam pertanyaan sebelumnya tentang mesin negara eksotis , Alex ten Brink dan Raphael membahas kemampuan komputasi dari jenis mesin negara yang aneh: min-heap automata. Mereka mampu menunjukkan bahwa himpunan bahasa yang diterima oleh mesin tersebut ( ) bukan merupakan himpunan bagian atau superset dari himpunan bahasa bebas konteks. Mengingat penyelesaian yang berhasil dan minat yang jelas pada pertanyaan itu, saya melanjutkan untuk mengajukan beberapa pertanyaan lanjutan.$HAL$

Diketahui bahwa automata hingga deterministic dan nondeterministic memiliki kemampuan komputasi yang setara, seperti halnya mesin Turing deterministic dan nondeterministic. Namun, kemampuan komputasi automata push-down deterministik kurang dari pada automata push-down nondeterministic.

Apakah kemampuan komputasi min-heap automata deterministik kurang dari, atau sama dengan, kemampuan min-heap automata non-deterministik?

Tampaknya untuk model ini, mesin non-deterministik tidak setara dengan yang deterministik, karena pada dasarnya alasan yang sama bahwa PDA deterministik tidak setara dengan yang non-deterministik.

Pertimbangkan bahasa (di mana adalah tanda khusus yang tidak terkandung dalam dan ).

Saya mengklaim bahwa mesin non-deterministik - dapat memutuskan bahasa ini: Ia melakukan sama dengan PDA untuk . Solusi PDA standar menggunakan stack hanya untuk menghitung offset: ia secara nondestinial menebak offset , mengingat nilai (menambahkan simbol ke stack pada setiap langkah), kemudian PDA mengabaikan input sampai menemukan , dan kemudian muncul simbol dari tumpukan sampai kosong. Pada tahap ini kita tepat berada di dan dia PDA dapat memeriksa apakah . (jika ada yang salah di tengah, PDA "mati"). Karena stack alphabet unary, maka dapat disimulasikan dengan mesin min-heap. Sebenarnya: apa saja$N$$HAL$$L$$i$$x_i$$\$$$y_i$$x_i \ne y_i$$L$ yang diterima oleh PDA dengan alfabet unary dapat diterima oleh mesin min-heap. (Saya mengabaikan, mungkin, tanda khusus lain ditambahkan untuk mengidentifikasi tumpukan kosong, tetapi tanda yang setara dapat ditambahkan ke tumpukan)

Untuk arah yang lain, saya tidak memiliki bukti formal, tetapi inilah pemikiran saya:

Saya mengklaim bahwa mesin deterministik - tidak mampu memutuskan bahasa ini. Secara intuitif, konten heap tidak dapat dikorelasikan dengan (jika tidak, permute . Konten heap tetap sama ..). Ini menunjukkan bahwa satu-satunya hal yang penting adalah jumlah elemen dalam heap, tetapi kemudian, jika - dapat memutuskan , maka dapat juga deterministic- .$D$$HAL$$x$$x$$D$$HAL$$L$$PDA$

Edit: detail lebih lanjut tentang klaim "permute ". Dengan asumsi dugaan Raphael ada dan bahwa setelah membacanya, konten heap adalah sama. Kemudian perhatikan kata-kata dan . Isi heap adalah sama ketika HAL sampai ke tanda dolar, sehingga ia harus menerima keduanya atau menolak keduanya. kontradiksi .$x$$x_1$$x_2$$x_1\$x_1$$x_2\$x_1$

Adakah yang melihat bukti langsung untuk dugaan itu?