Saat ini saya sedang melakukan penelitian Bahasa Formal yang melibatkan kelas-kelas bahasa di atas Reguler tetapi di bawah Konteks Gratis. Saya melihat hal-hal seperti Mesin Multicounter Berbalik-Pembalikan, mesin penghitung tumpukan tunggal, CFL deterministik, dll.
Saya ingin tahu apakah ada yang tahu buku bagus atau makalah survei yang menguraikan sifat-sifat bahasa ini. Sebagian besar yang saya lihat terlalu tidak jelas atau terlalu baru di buku Hopcroft-Ullman saya, bahkan edisi 1979.
Terutama saya sedang mencari kelas bahasa mana yang terkandung dalam satu sama lain, sifat penutupan bahasa ini, dan decidability masalah dasar (masalah-F) pada bahasa-bahasa ini.
Beberapa contoh hal yang saya cari dalam referensi ini:
- Apakah semua bahasa diterima oleh mesin Multi-counter yang terikat pembalikan juga diterima oleh mesin counter tunggal yang tidak berbalikan?
- Apakah bahasa MultiCounter terikat-pembalikan deterministik ditutup di bawah gabungan kiri dan kanan?
- Apakah universalitas dapat dipilih untuk mesin penghitung tunggal.
Ini hanya contoh pertanyaan, saya punya banyak pertanyaan lain yang muncul dalam pekerjaan saya sehari-hari.
Sebagai titik awal, saya sudah mencoba menelusuri makalah mana yang mengutip "Mesin Multicounter Pembalikan-Bounded Oscar Ibarra dan Masalah Keputusan Mereka", tetapi belum menemukan banyak.
sumber
Jawaban:
Bukan topik standar, tidak. Dan maaf, saya tidak memiliki gambaran umum.
Namun, saya akan melihat pada tesis PhD Klaus Reinhardt untuk setidaknya gambar dari berbagai keluarga yang tinggal di daerah ini. Lihat halaman 64 untuk diagram kebun binatang. Termotivasi oleh Petri Nets dengan busur inhibitor Reinhardt mempelajari multicounter prioritas dengan batasan kapan harus melakukan tes nol. Non-sepele.
Ngomong-ngomong, pertanyaan contoh terakhir Anda dibahas di forum ini oleh pengguna Sam Jones. Referensi Ibarra lainnya.
sumber