menghitung NFA minimal untuk DFA

17

Bertahun-tahun yang lalu saya mendengar bahwa menghitung NFA minimal (otomat hingga nondeterministik) dari DFA (deterministik) adalah pertanyaan terbuka, berlawanan dengan arah sebaliknya yang telah dikenal selama beberapa dekade dan diteliti dengan baik dengan efisien algoritma. Adakah yang datang dengan algoritma?O(nlg⁡n)

Pencarian cepat memberi saya makalah ini yang membuktikan bahwa itu pasti masalah yang sulit. Ternyata, tidak ada algoritma yang diberikan.

[1] Masalah NFA minimal sulit / Tao Jiang dan B. Ravikumar

Saya teringat masalah ini dengan pertanyaan berikut di situs CS.SE yang algoritma minimisasi DFA-> NFA akan berhubungan erat. Pertanyaan berikut ini menurut saya adalah level penelitian. Saya menyarankan bermigrasi ke TCS dan saya menulis jawaban yang menyarankan serangan statistik / empiris.

[2] Bagaimana kondisi untuk NFA agar DFA ekivalennya menjadi maksimal?

ds.algorithms reference-request fl.formal-languages automata-theory optimization vzn
sumber
4
Makalah yang Anda kutip menunjukkan kelengkapan PSPACE. Secara khusus, masalahnya ada di PSPACE, yang segera menyarankan algoritma. Algoritma apa yang Anda cari? Praktis dan / atau heuristik? Batas paling terkenal pada eksponen waktu berjalan? Sesuatu yang lain
Joshua Grochow
8
Sebenarnya itu tidak biasa. Sebelum masalah diketahui sebagai PSPACE-complete, semua upaya untuk mengembangkan algoritma yang efisien gagal, sehingga sedikit yang dipublikasikan. Setelah masalah diketahui sebagai PSPACE-complete, tidak ada yang mencoba mengembangkan algoritma yang efisien, karena mereka tahu mereka akan gagal, sehingga lebih sedikit yang dipublikasikan.
Jeffε
4
(1) Apa artinya “arah sebaliknya yang telah dikenal selama beberapa dekade dan diteliti dengan baik dengan algoritma O (n lg n) yang efisien”? DFA minimal untuk NFA dengan status n dapat memiliki ukuran eksponensial dalam n, sehingga diperlukan beberapa pengkodean keluaran nontrivial. (2) Tidak ada yang namanya "the" NFA minimal untuk bahasa reguler yang diberikan. Bandingkan ini dengan keberadaan DFA minimal.
Tsuyoshi Ito
1
JEFFE Anda memiliki poin yang baik tetapi saya yakin ada banyak masalah lengkap Pspace yang masih memiliki algoritma canggih yang memanfaatkan struktur masalah selain hanya menyebutkan semua solusi yang mungkin, benar? mengakui, saya tidak bisa memikirkan apa pun di luar kepala saya. mungkin kamu bisa? tebak itu akan menjadi pertanyaan menarik lainnya untuk diajukan di sini.
vzn
2
Sebuah+

Jawaban:

25

Ini benar-benar masalah yang keras kepala - dan dipelajari dengan baik. Mengenai hasil positif, algoritma yang tepat oleh Kameda dan Weiner, pendekatan heuristik oleh Polak, dan pendekatan baru-baru ini menggunakan pemecah SAT oleh Geldenhuys et al. masuk dalam pikiran. Tetapi tampaknya ada hasil yang jauh lebih negatif mengesampingkan pendekatan lain yang mungkin (misalnya algoritma aproksimasi, kasus khusus, model NFA yang kurang kuat, ...) Lihat di bawah untuk beberapa referensi.

T. Kameda dan P. Weiner. Pada keadaan minimal automata terbatas nondeterministic. Transaksi IEEE di Komputer, C-19 (7): 617-627, 1970.

A. Malcher. Meminimalkan automata terbatas adalah komputasi yang sulit. Ilmu Komputer Teoritis 327: 375-390, 2004.

L. Polák. Meminimalkan NFA menggunakan otomat universal. International Journal of Foundations of Computer Science, 16 (5): 999-1010, 2005.

G. Gramlich dan G. Schnitger. Meminimalkan NFA dan Ekspresi Reguler. Simposium tentang Aspek Teoritis Ilmu Komputer (STACS 2005), LNCS 3404, hlm. 399-411.

H. Gruber dan M. Holzer. Ketidakpastian keadaan nondeterministik dan kompleksitas transisi dengan asumsi P <> NP. Perkembangan dalam Teori Bahasa (DLT 2007), LNCS 4588, hlm. 205–216.

H. Gruber dan M. Holzer. Kompleksitas komputasi minimalisasi NFA untuk bahasa terbatas dan unary. Teori dan Aplikasi Bahasa dan Automata (LATA 2007), hlm. 261–272.

H. Björklund dan W. Martens. Perbatasan traktabilitas untuk meminimalkan NFA. Kolokium Internasional tentang Automata, Bahasa dan Pemrograman (ICALP 2008), LNCS 5126, hlm. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Mengurangi Finite Automata yang Tidak Menentukan dengan Pemecah SAT. Metode Negara Hingga dan Pemrosesan Bahasa Alami (FSMNLP 2009), LNCS 6062, 81–92.

EDIT (8 Juni 2015)

Pembaruan: Makalah berikut menyajikan algoritma heuristik untuk mengurangi ukuran Büchi automata nondeterministic, bersama dengan eksperimen pada automata acak. Seperti yang mereka nyatakan dalam kesimpulan, metode mereka juga berlaku untuk NFA: "Sementara kami mempresentasikan metode kami dalam konteks Büchi automata, kebanyakan dari mereka secara sepele membawa ke kasus automata yang lebih sederhana daripada kata-kata yang terbatas."

Richard Mayr, Lorenzo Clemente. Minimalisasi Automata Lanjutan. POPL 2013. Laporan Teknis yang Diperpanjang EDI-INF-RR-1414.

Alat baris perintah mereka Reduce v1.2 dapat dipanggil dengan opsi "-finite" untuk mengurangi NFA yang diberikan. Implementasinya adalah open source dan dirilis di bawah Lisensi Publik Umum GNU.

Hermann Gruber
sumber
3
Apakah Anda tahu jika ada implementasi open-source dari semua ini?
jmite
Hai Hermann, terima kasih banyak atas semua informasinya! Saya tahu bahwa diberi NFA, sulit untuk menemukan NFA setara terkecil. Tapi, bagaimana dengan yang berikut: Diberi DFA, cari NFA yang setara terkecil. Apakah ini sulit? Seberapa keras?
Michael Wehar
Maaf, saya mengerti sekarang! Makalah yang terdaftar pertama membahas hal ini: springerlink.com/content/y61724u571v487x5 Juga, makalah lain yang Anda cantumkan membahas ini untuk bahasa reguler terbatas: hermann-gruber.com/data/lata07-final.pdf Terima kasih telah mengklarifikasi ini untuk saya! :)
Michael Wehar