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.

— Lew Reyzin
źródło

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}$

— Yuval Filmus
źródło

Czy na pewno jest w PSPACE (jeśli nie, to byłby po prostu PSPACE-HARD)? A może wystarczy sprawdzić wszystkie ciągi o jakiejś wielomianowej długości, aby sprawdzić, czy wyrażenia regularne i DFA zgadzają się na nich wszystkich? Czy to oczywiste? :-)

— Neal Young

Pamiętaj, że osiągalność jest w NL, więc nawet jeśli DFA odpowiadający wyrażeniu regularnemu jest wykładniczy, ponieważ dostęp do Oracle jest tani, możemy dowiedzieć się, czy różnica symetryczna jest pusta czy nie w NPSPACE = PSPACE.

— Yuval Filmus

Nie widzę wyniku twardości. To znaczy, jak zredukujesz powyższy problem do uniwersalności wyrażeń regularnych?

— Markus

Wybierz DFA, który akceptuje wszystko. Aby pokazać twardość, redukujesz REGULARNĄ EKSPRESJĘ NIŻ UNIWERSALNOŚĆ do danego problemu.

— Yuval Filmus

@YuvalFilmus Dzięki za odniesienie! Prawdopodobnie powinieneś dodać swój pierwszy komentarz do swojej kompletności, w obu znaczeniach tego słowa :)

— Lev Reyzin