Apakah ada tes yang efisien untuk jika NFA menerima subset dari NFA lain?

Jadi, saya tahu bahwa menguji apakah bahasa reguler adalah himpunan bagian dari bahasa biasa dapat ditentukan, karena kita dapat mengonversi keduanya menjadi DFA, menghitung , dan kemudian menguji apakah bahasa ini kosong. $R$ $S$ $R \cap \bar{S}$

Namun, karena ini memerlukan konversi ke DFA, ada kemungkinan bahwa DFA, dan dengan demikian algoritma pengujian, akan bersifat eksponensial dalam hal jumlah status dalam input NFA.

Apakah ada cara yang diketahui untuk melakukan ini dalam waktu polinomial? Apakah masalah ini secara umum telah terbukti Co-NP lengkap?

Perhatikan bahwa masalahnya adalah di Co-NP sejak kata diterima oleh tetapi tidak oleh akan menjadi sertifikasi polinomial yang . $R$ $S$ $R \not \subseteq S$

EDIT: ini tidak benar, karena tidak ada jaminan bahwa kata seperti itu akan jumlahnya banyak di sejumlah negara.

algorithms regular-languages automata np-complete decision-problem Ya ampun
sumber

apakah ini pertanyaan teoretis, atau soal praktik? kadang-kadang untuk "distribusi" input tertentu yang dijumpai dalam praktik, masalah lengkap Pspace mungkin "runnable" dalam waktu P.

vzn

Idealnya teori, tetapi bukti yang saya kerjakan sangat didorong oleh pengujian komputer, yang berarti bahwa algoritma cepat pasti akan berguna.

jmite

jadi ya, ada algoritma straightfwd yang bekerja dengan hanya mengikuti transisi secara paralel untuk masing-masing dari dua mesin dan melacak set keadaan yang dihasilkan, agak seperti algoritma determinasi std. tidak tahu apakah itu dalam literatur di suatu tempat, itu sangat sederhana yang mengira itu. apakah Anda sudah menggunakan beberapa algoritma? akan sangat membantu jika Anda mengutipnya. juga rincian lebih lanjut tentang jenis input akan sangat membantu. itu juga terdengar seperti Anda ingin menentukan apakah persimpangan dua NFA kosong? Anda ingin bahasa persimpangan atau hanya Y / N jika tidak kosong?

vzn

Aku hanya mencari apakah itu kosong, ide yang saya cari jika untuk menguji apakah . Algoritma transisi paralel berfungsi, saya pikir bagian yang sulit adalah mengambil pujian dari NFA, Anda harus mengonversi ke DFA terlebih dahulu. Algoritme yang saya gunakan saat ini hanya brute-force, karena saya hanya berurusan dengan bahasa yang terbatas.

R - S = {}

$R-S=\{\}$

R \subseteq S

$R \subseteq S$

jmite

percaya mungkin ada cara untuk melintasi dua NFA tanpa mengkonversi baik ke DFA 1, bahkan menemukan pelengkap dari satu juga. tetapi belum melihatnya dalam referensi.

vzn

Jawaban:

Masalah dalam menentukan penahanan bahasa dalam NFA adalah -complete. Untuk membuktikan ini, mudah untuk mengurangi dari masalah universaility untuk NFA (menguji apakah ) Jadi, dengan cara tertentu, Anda harus menentukan, tetapi Anda dapat melakukannya sambil jalan. $PSPACE$ $L(A)=\Sigma^*$

Pengamatan Anda tentang ko-NP salah (tapi bagus). Saksi semacam itu memang dapat diperiksa dalam waktu polinomial di saksi , tetapi saksi terpendek itu sendiri mungkin eksponensial dalam panjang input. Karena , maka memutuskan non-penahanan juga -complete. $PSPACE=co-PSPACE$ $PSPACE$

Untuk hal-hal keadaan yang lebih hati-hati, memutuskan apakah adalah dalam ukuran (karena hanya yang perlu dilengkapi), dan dalam ukuran . $L(A)\subseteq L(B)$ $PSPACE$ $B$ $B$ $NLOGSPACE$ $A$

Shaull
sumber

Anda benar sekali. Saya telah berurusan dengan kelas khusus NFA di mana apa yang saya katakan berlaku, tetapi mungkin tidak dengan NFA umum tak terbatas. Terima kasih!

jmite

Anda tidak akan memiliki referensi ke kertas atau buku teks yang membuktikannya PSPACE-complete, bukan?

jmite

Ini bukan bukti yang sangat terperinci, tapi saya pikir itu akan berhasil: wisdom.weizmann.ac.il/~vardi/av/notes/lec4.ps

Shaull

Anda harus melihat kertas Jean-François Raskin Antichain Algorithms for Finite Automata .

Dalam percobaan kami, uji inklusi berbasis antikain melakukan satu atau dua urutan besarnya lebih baik daripada pendekatan "tradisional".

Jika saya ingat dengan benar, algoritma ini diterapkan di perpustakaan libAMoRE ++ .

Dan
sumber

Salah satu perpustakaan FSM terbaik, paling teliti dan sangat dioptimalkan, tersedia gratis secara online adalah perpustakaan F&T AT&T . Ini mengimplementasikan "perbedaan fsm" persis seperti yang Anda gambarkan, membutuhkan FSM bebas epsilon yang ditentukan untuk melakukan perbedaan. Satu ide adalah untuk meminimalkan satu atau kedua FSM sebelum melakukan perbedaan, yang mungkin membantu dalam beberapa kasus. (Yaitu penentuan tidak sama dengan meminimalkan.) Paket ini juga memiliki minimalisasi "perkiraan" atau "serakah" yang dirancang mungkin lebih cepat dari minimalisasi penuh.

Namun, mempelajari masalah yang sama, saya percaya ada beberapa generalisasi atau konstruksi FSM yang tidak muncul dalam literatur yang dapat membantu dengan masalah ini dengan menghindari langkah determinisasi, yaitu pada dasarnya membalikkan NFA tanpa membuat tambahan FSM yang ditentukan. Idenya adalah untuk melintasi tepi NFA "secara paralel" dan melacak set node yang merupakan bagian dari "superstate" saat ini (set negara) seperti halnya dengan algoritma penentuan standar. Kemudian, komplemen NFA menerima jika dan hanya jika set node superstate saat ini "semua tidak dapat menerima" (berbeda dengan konstruksi yang menentukan yang menerima jika "ada menerima").

Namun, saya belum pernah melihat ini ditulis sebelumnya dan tidak melihatnya melalui pencarian online cepat. Ada banyak referensi yang menyarankan atau menyiratkan bahwa satu-satunya cara untuk bekerja dengan komplemen NFA adalah dengan menentukannya.

Berikut adalah dua referensi "terdekat" yang mungkin berguna untuk beberapa ide. Saya akan tertarik untuk mendengar ada / orang lain yang "lebih dekat". Anda menyebutkan Anda sedang mengerjakan verifikasi program, yang mungkin merupakan bidang yang memiliki lebih banyak riset langsung tentang masalah tersebut.

[1] Konstruksi titik-temu dari Finata Automata Nondeterministic menggunakan Notasi Nazir Ahmad Zafar, Nabeel Sabir, dan Amir Ali

[2] Konstruksi Pelengkap untuk Nondeterministic Automata pada Infinite Words Orna Kupferman dan Moshe Vardi

vzn
sumber