Apa model automaton terkemuka yang mengandung polinomially-decidable?

Saya mencoba untuk memecahkan masalah tertentu, dan saya pikir saya mungkin bisa menyelesaikannya dengan menggunakan teori automata. Saya bertanya-tanya, model automata apa yang memiliki penahanan yang dapat ditentukan dalam waktu polinomial? yaitu jika Anda memiliki mesin Anda dapat menguji apakah efisien.$M_1, M_2$$L(M_1) \subseteq L(M_2)$

Yang jelas yang terlintas dalam pikiran adalah DFA dan mesin penghitung pembalikan di mana jumlah penghitung ditetapkan (lihat makalah ini ).

Apa kelas penting lainnya yang dapat ditambahkan ke daftar ini?

Semakin kuat automata, semakin baik. Sebagai contoh, DFA's tidak cukup untuk menyelesaikan masalah saya, dan mesin penghitung tidak dapat melakukannya dengan jumlah counter tetap. (Tentu saja, jika Anda menjadi terlalu kuat, maka penahanan tidak bisa dilakukan, seperti untuk NFA, atau tidak dapat dipastikan, untuk CFG).

Automata pushdown yang terlihat jelas (atau automata kata bersarang , jika Anda lebih suka bekerja dengan kata-kata bersarang daripada kata -kata terbatas) memperluas kekuatan ekspresif automata terbatas deterministik: kelas bahasa reguler secara ketat terkandung dalam kelas bahasa pushdown yang terlihat. Untuk automata yang jelas terlihat pushdown, masalah inklusi bahasa dapat diselesaikan dalam waktu polinomial. Untuk lebih jelasnya, lihat kertas karya Alur dan Madhusudan, khususnya Bab 6.

By the way, varian nondeterministic dari automata tampak pushdown secara eksponensial lebih singkat daripada varian deterministik, tetapi ada masalah bahasa inklusi adalah EXPTIM-lengkap dan dengan demikian tidak bisa diterapkan.

Alur, R .; Madhusudan, P. (2009). + Msgstr " Menambahkan struktur bersarang ke kata - kata ". Jurnal ACM 56 (3): 1–43.

Jika kata-kata tak terbatas berada dalam ruang lingkup Anda, Anda dapat menggeneralisasi DFA (dengan kondisi paritas) ke apa yang disebut Good-for-Games automata (GFG), yang masih memiliki penahanan polinomial.

NFA adalah GFG jika ada strategi , yang memberikan awalan baca sejauh ini dan keadaan saat ini dan huruf, memilih transisi untuk menuju ke negara berikutnya. Strategi σ harus memastikan bahwa untuk setiap w dalam bahasa otomat, run yang dihasilkan oleh σ pada w menerima.$\sigma:A^*\times Q\times A\to \Delta$$\sigma$$w$$\sigma$$w$

Containment untuk automata ini ada di P untuk kondisi paritas tetap (dengan mengurangi ke parity game), dan di Quasi-P jika indeks paritas adalah bagian dari input. Mereka bisa secara eksponensial lebih kecil daripada DFA yang setara [3].

Namun pada kata-kata yang terbatas, mereka hanya DFA dengan kemungkinan transisi tambahan yang tidak berguna, sehingga mereka tidak benar-benar membawa sesuatu yang baru.

Berikut ini beberapa referensi:

[1] Memecahkan game tanpa determinasi , Henzinger, Piterman, di CSL 2006

[2] Nondeterminisme di hadapan masa depan yang beragam atau tidak diketahui , Boker, Kuperberg, Kupferman, Skrzypczak, di ICALP 2013

[3] Tentang Penentuan Good-for-Games Automata , Kuperberg, Skrzypczak, di ICALP 2015

Sebuah Non deterministik XOR otomat (NXA) sesuai dengan pertanyaan Anda.

$M$$w\in \Sigma^*$$L(M)$

NXA digunakan untuk membuat representasi kecil dari bahasa reguler serta beberapa algoritma parametrized.

$O(|Q|^3$$L(M_1)\subseteq L(M_2)$

$M_1$$M_2$$L(M_2)$$L(M_1)$

$M_2$

Biarkan saya membuat sketsa bukti dari hasil ini.

$M_1$$M_2$$M_2$$L(M_1)\subseteq L(M_2)$

Bukti.
Langkah 1: Hal ini mengurangi universalitas automata yang tidak ambigu.

$M_1$$M_1$

$L(M_1)\subseteq L(M_2)$$L(M_2)\cup L(M_1)^c$

Langkah 2: Kebetulan automata yang ambigu dapat dilihat sebagai NXA automata (Non-deterministic XOR automata pada posting sebelumnya oleh RB) tanpa ada evaluasi yang harus diubah (memang, disjungsi atas semua run accpeting setara dengan xor atas semua penerimaan berjalan karena paling banyak ada satu run yang demikian). Untuk automata ini, universalitas dikenal sebagai polinomial (QED).

$Z/2Z$

[SH85] Richard E. Stearns dan Harry B. Hunt III. Pada masalah kesetaraan dan kontainmen untuk ekspresi reguler yang tidak ambigu, tata bahasa reguler dan automata terbatas. SIAM J. Comput., 14 (3): 598–611, 1985.

[S61] Schützenberger, MP: Tentang definisi keluarga automata. Informasi dan Kontrol 4, 245–270 (1961)

Tata bahasa LL (k) reguler (yaitu tata bahasa yang keduanya LL (k) dan reguler ) dapat dikonversi dalam waktu polinomial menjadi automata terbatas deterministik yang setara, dan dengan demikian penahanan bahasa dan kesetaraan dapat diselesaikan dalam PTIME. Lihat Teorema 4.2 dalam makalah berikut (dan hasilnya setelah itu untuk aplikasi pengamatan ini ke skema program).

Harry B. Hunt III: Pengamatan pada Kompleksitas Masalah Ekspresi Reguler , Jurnal Ilmu Komputer dan Sistem 19, 222-236 (1979)