Jak szybko możemy zdecydować, czy dany DFA jest minimalny?

Minimalizowanie deterministycznych automatów skończonych (DFA) to problem, który został dokładnie przestudiowany w literaturze, i zaproponowano kilka algorytmów w celu rozwiązania następującego problemu: Biorąc pod uwagę DFA , oblicz odpowiednią minimalną DFA akceptującą ten sam język, co \ mathscr {A} . Większość tych algorytmów działa w czasie wielomianowym.$\mathscr{A}$$\mathscr{A}$

Zastanawiam się jednak, czy wariant decyzyjny tego problemu - „biorąc pod uwagę DFA $\mathscr{A}$ , czy $\mathscr{A}$ minimalny?” - można rozwiązać bardziej efektywnie niż obliczanie minimalnego automatu. Oczywiście można to również zrobić skutecznie, uruchamiając na przykład algorytm zawężania partycji Hopcroft, a następnie decydując, czy wszystkie partycje zawierają dokładnie jeden stan.

Jak sugeruje Yuval Filmus w swojej odpowiedzi , wariant rozstrzygalności można rozwiązać szybciej, być może przy użyciu standardowych algorytmów. Niestety nie rozumiem, jak to zrobić (mam nadzieję, że nie umknie mi tutaj oczywista kwestia).

Yuval wskazuje w komentarzach tutaj, że najbardziej znane algorytmy (takie jak powyższy) działają w czasie $\mathcal{O}(n \log n)$ dla alfabetów o stałej wielkości. Dlatego jestem nie tylko zainteresowany asymptotycznie znaczącym wzrostem czasu wykonywania, ponieważ wydaje się to raczej mało prawdopodobne. Najbardziej niepokoi mnie to, że nie wyobrażam sobie żadnego „skrótu”, który mógłby wynikać z faktu, że interesuje nas tylko odpowiedź „tak-nie-odpowiedź” - nawet skrótu, który pozwala zaoszczędzić asymptotycznie nieistotną ilość czasu. Uważam, że każdy rozsądny algorytm decydujący o minimalności DFA musiałby faktycznie zminimalizować DFA i sprawdzić, czy coś się zmieni w trakcie procesu.

Być może nie jest to dokładnie taka odpowiedź, jakiej szukasz, ale ponieważ pytałeś o problemy decyzyjne, pomyślałem, że możesz być zainteresowany złożonością problemu. Jest -kompletny.$\mathsf{NL}$

Co to znaczy, że DFA jest minimalne? Istnieją dwie właściwości:

1. Każdy stan jest osiągalny: tak, że możemy osiągnąć ze stanu początkowego , wykonując ; w symbolach: . q s w s → w$\forall q \in Q \; \exists w \in \Sigma^*$$q$$s$$w$$s \rightarrow_w q$

2. Każda para stanów jest rozróżnialna: with tak, że i i (tylko jeden z jest stanem akceptacji).q ≠ r ∃ w ∈ Σ ∗ q → w s r → w t | { s , t } ∩ F | = 1 s , $\forall q,r \in Q$$q \neq r$ $\exists w \in \Sigma^*$$q \rightarrow_w s$$r \rightarrow_w t$$|\{s,t\} \cap F| = 1$$s,t$

Zauważ, że mogą być obliczane w dzienniku przestrzeni (tj , wystarczy śledzić aktualną pozycję, jak postępować jednym z listów na raz). Ponadto istnieje tylko skończona liczba odmian między i więc w wyniku twierdzenia Immerman-Szelepcsenyi mamy problem z .L w ∀ ∃ N $x \rightarrow_w y$$\mathsf{L}$$w$$\forall$$\exists$$\mathsf{NL}$

Najprostszym sposobem widać, że jest trudno jest, aby zauważyć, że własność 1 rozwiązuje - skierowanej unreachability, który jest prototypowym trudnym problemem. Ale nawet jeśli weźmiesz pod uwagę tylko osiągalne DFA, problem jest nadal trudny (tj. Właściwość 2 to -hard) i możesz znaleźć stosunkowo prosty dowód w Lemma 2.2 z Cho & Huynh (1992) . s $\mathsf{NL}$$s$$t$$\mathsf{NL}$

Oczywiście użyłem niedeterminizmu, więc jest to trochę kaszel w odróżnieniu od algorytmu Hopcrofta. Wiemy jednak, że , więc możesz użyć tych konstrukcji, aby uzyskać bardziej efektywny pod względem przestrzeni algorytm niż Hopcroft (który ze swej natury musi śledzić wielu partycji ).$\mathsf{NL} \subseteq \mathsf{L}^2$$n$