Dla których wyrażeń regularnych

21

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

Biorąc pod uwagę wyrażenie regularne , czy L ( β ) = Σ ?β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 ( α ) ?βL(β)=L(α)

Znane są następujące:

  • Dla problemem jest PSPACE-completeα=(0+1)

  • 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)?α

mikero
źródło
3
α

Odpowiedzi:

17

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

  • L(α)
  • L(α)L(α)w1w2wkw1,,wk
  • 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 )

David
źródło
3
Komentarz do poprzedniej odpowiedzi (nie mam wystarczającej liczby przedstawicieli na tej stronie, aby móc komentować): Nie sądzę, że może to być właściwe. Jest to klasyczny wynik Meyera-Stockmeyera (Twierdzenie 6.1 z [2]), że uniwersalność dla jednorzędowych języków regularnych jest coNP-pełna. [2] LJ Stockmeyer i AR Meyer. 1973. Problemy ze słowami wymagające czasu wykładniczego (raport wstępny). W materiałach z piątego dorocznego sympozjum ACM na temat teorii obliczeń (STOC '73). ACM, Nowy Jork, Nowy Jork, USA, 1-9
David
2
k=1|w1|=1