Kompleksitas parameterisasi penyertaan bahasa reguler

Saya tertarik dengan masalah klasik REGULAR LANGUAGE INCLUSION. Diberi ekspresi reguler , kami menunjukkan oleh L ( E ) bahasa reguler yang terkait dengannya. (Ekspresi reguler menggunakan alfabet tetap Σ , dengan gabungan operasi, bintang Kleene dan gabungan.)$E$$L(E)$$\Sigma$

Input: Dua ekspresi reguler dan E 2 Pertanyaan: Benarkah L ( E 1 ) ⊆ L ( E 2 ) ?$E_1$$E_2$
$L(E_1)\subseteq L(E_2)$

INCLUSI BAHASA REGULER dikenal sebagai PSPACE-complete [1].

Cara klasik untuk menyelesaikannya (dalam PSPACE) adalah dengan membangun NFA dan A 2 yang terkait dengan E 1 dan E 2 , untuk membangun DFA D 2 dari A 2 , melengkapinya menjadi DFA D C 2 , dan akhirnya, membangun otomat persimpangan A P dari A 1 dan D C 2 yang sesuai dengan persimpangan L ( E 1 ) dan L ( E 2 ) $A_1$$A_2$$E_1$$E_2$$D_2$$A_2$$D_2^C$$A_P$$A_1$$D_2^C$$L(E_1)$$L(E_2)^C$. Sekarang jika dan hanya jika tidak ada jalur menerima di A P .$L(E_1)\subseteq L(E_2)$$A_P$

Jika saya tidak salah, seluruh proses dapat dilakukan dalam waktu polinomial ketika adalah bahasa tetap, karena satu-satunya ledakan eksponensial berasal dari mengubah A 2 menjadi D 2 . Lebih baik lagi, masalahnya adalah FPT ketika diparameterisasi dengan | E 2 | , panjang E 2 .$E_2$$A_2$$D_2$$|E_2|$$E_2$

Ini memotivasi pertanyaan saya:

Pertanyaan: Ketika adalah ekspresi tetap, apa kompleksitas dari INCLUSI BAHASA REGULER? Apakah ini tetap PSPACE-selesai?$E_1$

[1] LJ Stockmeyer dan AR Meyer. Masalah kata yang membutuhkan waktu eksponensial: laporan pendahuluan. Prosiding Simposium ACM tahunan kelima tentang Teori Komputasi, STOC '73, hlm. 1-9.

Catatan: Menjadi non-ahli dalam bidang ini, saya menemukan [1] (dan makalah terkait pada waktu itu) sangat tidak dapat dibaca, dan tidak dapat menemukan bukti lain dari kelengkapan PSPACE - penunjuk ke bukti modern, seperti di sebuah buku, sangat welcome! Juga, para penulis tampaknya memungkinkan mengkuadratkan dalam ekspresi reguler mereka, yang saat ini agak tidak standar, saya percaya.)

$E_1$$E_1=\Sigma^*$

Memang sulit untuk menemukan bukti kekerasan-PSPACE modern yang dapat dibaca untuk universalitas ekspresi reguler, seperti yang sekarang dianggap sebagai cerita rakyat. Berikut adalah skema bukti cepat yang memungkinkan Anda untuk membuat ulang bukti:

---

$M$$\Sigma$$p(n)$$w\in\Sigma^*$$M$$e$$M$$w$

$L_M$$\$C_0\$ C_1\$\dots\$ C_f\$$$C_i$$M$$p(n)$$C_0$$w$$C_f$$C_i\to C_{i+1}$$M$$L_M$$M$

$e$$\Sigma'=\Sigma\cup\{\$\}$$e$$L_M$$L_M$$e$$e_1+e_2+\dots+e_k$$e_i$

$$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$ $C_i$$p(n)$$C_i$$C_{i+1}$$C_i$$C_{i+1}$$t(\Sigma')^{p(n)}t'$$t$$t'$$M$ $$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$$ oleh karena itu kami mengurangi (secara polinomi) masalah PSPACE yang sewenang-wenang menjadi universalitas ekspresi reguler. Saya meninggalkan beberapa detail, tetapi ini harus memungkinkan Anda untuk membangun bukti lengkap.

---

$E_1$

$(\Sigma')^{p(n)}$$p(n)$$p(n)$

[1] Tentang kesetaraan, penahanan, dan peliputan masalah untuk bahasa reguler dan bebas konteks Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Jurnal Ilmu Komputer dan Sistem. Volume 12, Edisi 2, April 1976, Halaman 222-268

[2] Masalah kesetaraan untuk ekspresi reguler dengan kuadrat membutuhkan ruang eksponensial . Meyer, AR dan L. Stockmeyer. Simposium IEEE ke-13 tentang Switching dan Automata Theory, Okt 1972, hlm.125–129.