Powszechnie wiadomo, że następujący problem jest związany z PSPACE:
Biorąc pod uwagę wyrażenie regularne , czy L ( β ) = Σ ∗ ?
Co z określeniem równoważności z innymi (stałymi) wyrażeniami regularnymi ?
Biorąc pod uwagę wyrażenie regularne , czy L ( β ) = L ( α ) ?
Znane są następujące:
Dla problemem jest PSPACE-complete
Dla lub bardziej ogólnie α, który opisuje zbiór skończony, problem można rozstrzygać w czasie wielomianowym.
Wydaje mi się również prawdopodobne, że problem występuje w P, jeśli jest językiem jednoargumentowym.
Więc moje pytania to:
Dla którego powyższy problem decyzyjny PSPACE jest kompletny? Czy istnieje pełna charakterystyka?
Czy są jakieś dla których problem decyzyjny ma jakąś pośrednią złożoność (jak NP-zupełny)?
Odpowiedzi:
To pytanie jest omówione w sekcji 2 [1], która pokazuje (Twierdzenie 2.6), że problem jest
[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 )
źródło