meminimalkan ukuran ekspresi reguler untuk set yang terbatas

Diketahui bahwa meminimalkan ukuran ekspresi reguler adalah PSPACE-complete bahkan jika kita memiliki DFA sebagai spesifikasi bahasa .

Apa hasil jika bahasanya terbatas?

Satu dapat mempertimbangkan masalah ini dalam dua model:

1. Input adalah semua string dalam bahasa, dan kami mengukur ukuran input dengan jumlah panjang semua string.
2. Input adalah DFA, dan kami mengukur ukuran input dengan jumlah status DFA.

Bintang Kleene tidak berguna dalam kasus hingga, jadi hanya , | dan ⋅ (penggabungan) digunakan dalam ekspresi. Tentu saja, panjang ekspresi reguler tampak sewenang-wenang. Sebagai gantinya, seseorang dapat memberi bobot pada setiap operasi (termasuk menambahkan tanda kurung), dan meminta untuk meminimalkan bobot ekspresi reguler.$()$$|$$\cdot$

Sunting: Seperti yang dicatat adrianN, ini terkait dengan kode berbasis tata bahasa. Ini NP-complete untuk menghasilkan tata bahasa bebas konteks panjang minimum untuk menggambarkan set yang terbatas. Tidak jelas mengapa tata bahasa bebas konteks ukuran minimum dapat menyiratkan banyak tentang ekspresi reguler ukuran minimum. Mungkin aturan penulisan ulang yang cerdas dapat menghubungkan keduanya, dan membuktikan bahwa pada model pertama, masalahnya ada di NP.

Argumen berikut ini pada dasarnya dari ( 1 ): Versi keputusan dari dua masalah terkandung dalam tingkat kedua hirarki polinomial (lebih tepatnya: di kelas kompleksitas ), sebagai berikut. Tebak ekspresi ukuran reguler paling banyak $\Sigma^P_2$$k$ , dan periksa apakah itu setara dengan otomat terbatas deterministik yang diberikan (masing-masing: dengan bahasa yang diberikan sebagai daftar kata).

Saya percaya bahwa tidak ada hasil lebih lanjut mengenai masalah Anda yang diketahui. Untuk masalah pengoptimalan yang tampak serupa, di mana tujuannya adalah untuk menemukan otomat hingga nondeterministik setara minimum dan bukan ekspresi reguler, hasil berikut diketahui:

• Untuk input yang dideskripsikan sebagai DFA, masalah NFA minimum yang ekivalen adalah -hard, lihat ( 1 ). Di sini, D P singkatan dari "perbedaan waktu polinomial"; ini adalah kelas kompleksitas "Sigma" di tingkat kedua hierarki Boolean .${\bf DP}$${\bf DP}$
• Untuk input yang diuraikan sebagai daftar kata, masalah NFA minimum yang ekivalen adalah -hard, lihat ( 2 ).${\bf NP}$
• Untuk dan input yang dideskripsikan sebagai tabel kebenaran, masalah NFA ekivalen minimum adalah N P -complete, lihat ( 2 ).$L \subseteq \{0,1\}^m$${\bf NP}$

Waspadalah: Tidak seperti pengaturan bahasa tak terbatas, saya tidak melihat pengurangan langsung dari kasus minimalisasi NFA ke masalah dari pertanyaan Anda.

Referensi:

(1) Hermann Gruber dan Markus Holzer. Kompleksitas Komputasi Minimisasi NFA untuk Bahasa Terbatas dan Unary . Dalam: Konferensi Internasional Pertama tentang Teori dan Aplikasi Bahasa dan Automata (LATA 2007), hlm. 261-272, 2007.

(2) Hermann Gruber dan Markus Holzer. Ketidakpercayaan dari Keadaan Tidak Menentu dan Kompleksitas Transisi dengan Mengasumsikan P <> NP . Dalam: Konferensi Internasional ke-11 tentang Perkembangan Teori Bahasa (DLT 2007), LNCS 4588, hlm. 205-216, 2007.

$L=\{w\}$$w$

tampaknya kurang memiliki jawaban yang diketahui dengan pasti atau yang lebih baik dari ini, inilah referensi hampir / baru-baru ini tentang penelitian khususnya tentang subjek meminimalkan REs (yang tampaknya merupakan sudut yang tidak biasa):

Meminimalkan NFA dan Ekspresi Reguler (2005) oleh Gregor Gramlich, Georg Schnitger

Kami menunjukkan hasil yang tidak dapat diperkirakan mengenai minimalisasi automata terbatas nondeterministik (nfa) serta ekspresi reguler relatif terhadap nfa, ekspresi reguler atau automata terbatas deterministik (dfa). Kami menunjukkan bahwa tidak mungkin untuk meminimalkan secara efisien nfa yang diberikan atau ekspresi reguler dengan n status, transisi, resp. simbol dalam faktor o (n), kecuali P = PSPACE. Hasil ketidaksanggupan kami untuk dfa yang diberikan dengan keadaan n didasarkan pada asumsi kriptografi dan kami menunjukkan bahwa algoritma yang efisien akan memiliki faktor perkiraan setidaknya poli (log n). Pengaturan kami juga memungkinkan kami untuk menganalisis masalah dfa konsisten minimum.