Dla których wyrażeń regularnych

Powszechnie wiadomo, że następujący problem jest związany z PSPACE:

Biorąc pod uwagę wyrażenie regularne , czy L ( β ) = Σ ∗ ?$\beta$$L(\beta) = \Sigma^*$

Co z określeniem równoważności z innymi (stałymi) wyrażeniami regularnymi ?$\alpha$

Biorąc pod uwagę wyrażenie regularne , czy L ( β ) = L ( α ) ?$\beta$$L(\beta) = L(\alpha)$

Znane są następujące:

• Dla problemem jest PSPACE-complete$\alpha = (0+1)^*$

• Dla lub bardziej ogólnie α, który opisuje zbiór skończony, problem można rozstrzygać w czasie wielomianowym.$\alpha = \emptyset$$\alpha$

Wydaje mi się również prawdopodobne, że problem występuje w P, jeśli jest językiem jednoargumentowym.$\alpha$

Więc moje pytania to:

Dla którego powyższy problem decyzyjny PSPACE jest kompletny? Czy istnieje pełna charakterystyka?$\alpha$

Czy są jakieś dla których problem decyzyjny ma jakąś pośrednią złożoność (jak NP-zupełny)?$\alpha$

To pytanie jest omówione w sekcji 2 [1], która pokazuje (Twierdzenie 2.6), że problem jest

• $L(\alpha)$
• $L(\alpha)$$L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$$w_1,\ldots, w_k$
• W innym przypadku PSPACE-complete.

[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymański, O równoważności, ograniczeniu i problemach dotyczących języków regularnych i bezkontekstowych, Journal of Computer and System Sciences, tom 12, wydanie 2, 1976 , Strony 222-268, ISSN 0022-0000, http://dx.doi.org/10.1016/S0022-0000(76)80038-4 . ( http://www.sciencedirect.com/science/article/pii/S0022000076800384 )