Koszt zapytania o równoważność dla DFA

Zainspirowany tym pytaniem ciekawi mnie:

Jaka jest najgorsza złożoność sprawdzania, czy dany DFA akceptuje ten sam język jako dane wyrażenie regularne?

Czy to jest znane? Można mieć nadzieję, że ten problem występuje w P - że algorytm ma wielomian wielkości obu.

Według Garey i Johnsona (s. 174) REGULARNA EKSPRESJA NIŻ UNIWERSALNOŚĆ jest pełna na PSPACE. To jest problem z podjęciem decyzji, czy wyrażenie regularne nad ma nie generować wszystkie sznurki. Twój problem jest więc kompletny dla PSPACE.$\{0,1\}$

Oto jeden ze sposobów, aby przekonać się, że problemem PO jest PSPACE. Biorąc pod uwagę DFA i wyrażenie regularne , skonstruuj NFA dla , i użyj konstrukcji zestawu mocy do wirtualnej budowy DFA równoważnej ; nie będziemy przechowywać w pamięci, ale mamy dostęp do Oracle, używając tylko przestrzeni wielomianowej. Teraz wirtualnie skonstruuj DFA dla symetrycznej różnicy i używając konstrukcji produktu. Ten DFA nie przyjmuje żadnych ciągów znaków (a więc$A$$r$$B$$r$$C$$B$$C$$C$$D$$A$$C$$L(A) = L(r)$), jeśli nie ma ścieżki ze stanu początkowego do stanu akceptacji. Ponieważ osiągalność jest w NL, a ma rozmiar , możemy sprawdzić, czy w , ta ostatnia równość wynika z twierdzenia Savitcha.$D$$2^{\mathrm{poly}(n)}$$L(D) = \emptyset$$\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$