Untuk ekspresi reguler mana adalah PSPACE-complete?

Diketahui bahwa masalah berikut ini adalah PSPACE-complete:

Diberi persamaan reguler , apakah ?L ( β ) = Σ $\beta$$L(\beta) = \Sigma^*$

Bagaimana dengan menentukan ekivalensi dengan persamaan reguler (tetap) ?$\alpha$

Diberi persamaan reguler , apakah ?L ( β ) = L ( α $\beta$$L(\beta) = L(\alpha)$

Berikut ini diketahui:

• Untuk , masalahnya adalah PSPACE-complete$\alpha = (0+1)^*$

• Untuk , atau lebih umum yang menjelaskan himpunan berhingga, masalahnya dapat ditentukan dalam waktu polinomial.$\alpha = \emptyset$$\alpha$

Sepertinya juga bagi saya bahwa masalahnya adalah P jika adalah bahasa yang unary.$\alpha$

Jadi pertanyaan saya adalah:

Untuk manakah masalah keputusan di atas selesai-PSPACE? Apakah ada karakterisasi lengkap?$\alpha$

Apakah ada yang masalah keputusannya memiliki beberapa kompleksitas menengah (seperti NP-complete)?$\alpha$

Pertanyaan ini dibahas dalam Bagian 2 dari [1], yang menunjukkan (Teorema 2.6) bahwa masalahnya adalah

• dalam P jika terbatas;$L(\alpha)$
• coNP-complete jika tidak terbatas tetapi dibatasi (yaitu untuk beberapa );L ( α ) ⊆ w ∗ 1 w ∗ 2 … w ∗ k w 1 , … , w $L(\alpha)$$L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$$w_1,\ldots, w_k$
• Selesaikan PSPACE sebaliknya.

[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, Tentang kesetaraan, penahanan, dan mencakup masalah untuk bahasa reguler dan bebas konteks, Jurnal Ilmu Komputer dan Sistem, Volume 12, Edisi 2, 1976 , Halaman 222-268, ISSN 0022-0000, http://dx.doi.org/10.1016/S0022-0000(76)80038-4 . ( http://www.sciencedirect.com/science/article/pii/S0022000076800384 )