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 . 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.

algorithms formal-languages finite-automata

— Marka Cornelius
źródło

Algorytm Hopcrofta działa już w quasi-liniowym czasie, więc nie ma zbyt wiele miejsca na ulepszenia.

— Yuval Filmus

Tak, zredagowałem moje pytanie, aby odzwierciedlało ten fakt, @YuvalFilmus

— Cornelius Brand

Uważam, że najszybszym znanym algorytmem minimalizacji DFA jest nadal ten . Jest szybszy niż jakikolwiek algorytm opublikowany przed 2008 r. Działający w czasie , gdzie jest liczbą przejść.

O (n + m \log n)

$O(n+m \log n)$

m

$m$

— Juho

wydaje mi się mało prawdopodobne, że problem decyzyjny jest równorzędny ze złożonością do problemu minimalizacji, ten pierwszy wydaje się być prawdopodobnie trudniejszy, ponieważ wiąże się z testowaniem równoważności DFA, co nie jest nietrywialne. wydaje się więc, że złożoność problemu decyzyjnego stanowi maksimum „testu minimalizacji lub równoważności”. i jaka jest złożoność testu równoważności?

— vzn

@vzn Zakładając, że miałeś na myśli „[...] co nie jest łatwe”: Nie musi to koniecznie, ponieważ np. procedura, którą podałem w moim pytaniu, pozwala uniknąć sprawdzania równoważności. Myślę jednak, że problem nie jest łatwiejszy niż minimalizacja.

— Cornelius Brand

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:

Każdy stan jest osiągalny: tak, że możemy osiągnąć ze stanu początkowego , wykonując ; w symbolach: . $\forall q \in Q \; \exists w \in \Sigma^*$ $q$ $s$ $w$ $s \rightarrow_w q$
Każda para stanów jest rozróżnialna: with tak, że i i (tylko jeden z jest stanem akceptacji). $\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 . $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) . $\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$

— Artem Kaznatcheev
źródło

wydaje się to poprawiać przestrzeń, ale nie złożoność czasu?

— dniu

Zgadzam się z vzn. Chociaż podoba mi się ta odpowiedź, nadal interesują mnie spostrzeżenia, które są bliżej związane z pierwotnym pytaniem.

— Cornelius Brand

@ C.Brand Moja odpowiedź ma być styczna (stąd wyłączenie odpowiedzialności na początku;)) Właśnie podałem wam najniższą klasę złożoności, dla której wiem, że problem jest kompletny. Istnieje standardowa technika konwersji algorytmów algorytmy (tj. BFS na wykresie konfiguracji ), ale nie sądzę, że konstrukcja da ci szybszy algorytm czasu.

N L

$\mathsf{NL}$

P

$\mathsf{P}$

— Artem Kaznatcheev