Wie schnell können wir entscheiden, ob ein bestimmter DFA minimal ist?

Das Minimieren deterministischer endlicher Automaten (DFAs) ist ein Problem, das in der Literatur gründlich untersucht wurde, und es wurden verschiedene Algorithmen vorgeschlagen, um das folgende Problem zu lösen: Berechnen Sie bei gegebenem DFA einen entsprechenden minimalen DFA, der dieselbe Sprache wie A akzeptiert . Die meisten dieser Algorithmen laufen in Polynomzeit.$\mathscr{A}$$\mathscr{A}$

Ich frage mich jedoch, ob die Entscheidungsvariante dieses Problems - "bei einem DFA ist A minimal?" - kann effizienter gelöst werden als die Berechnung des Minimalautomaten. Dies kann natürlich auch effizient erfolgen, indem beispielsweise der Partitionsverfeinerungsalgorithmus von Hopcroft ausgeführt und dann entschieden wird, ob alle Partitionen genau einen Status enthalten.$\mathscr{A}$$\mathscr{A}$

Wie Yuval Filmus in seiner Antwort vorschlägt , kann die Entscheidbarkeitsvariante schneller gelöst werden, möglicherweise unter Verwendung der Standardalgorithmen. Leider kann ich nicht sehen wie (ich hoffe, ich vermisse hier keinen offensichtlichen Punkt).

Yuval weist in den Kommentaren hier darauf hin, dass die bekanntesten Algorithmen (wie der obige) in der Zeit für Alphabete konstanter Größe ausgeführt werden. Daher bin ich nicht nur an asymptotisch signifikanten Laufzeitgewinnen interessiert, da diese eher unwahrscheinlich erscheinen. Was mich am meisten stört, ist, dass ich mir keine "Abkürzung" vorstellen kann, die sich aus der Tatsache ergibt, dass wir nur an einer Ja-Nein-Antwort interessiert sind - nicht einmal an einer Abkürzung, die es ermöglicht, asymptotisch vernachlässigbare Zeit zu sparen. Ich bin der Meinung, dass jeder vernünftige Algorithmus, der über die Minimalität eines DFA entscheidet, den DFA tatsächlich minimieren und prüfen muss, ob sich während des Prozesses etwas ändert.$\mathcal{O}(n \log n)$

Dies ist möglicherweise nicht genau die Art von Antwort, nach der Sie suchen, aber da Sie nach Entscheidungsproblemen gefragt haben, dachte ich, dass Sie an der Komplexität des Problems interessiert sein könnten. Es ist vollständig.$\mathsf{NL}$

Was bedeutet es nun, dass ein DFA minimal ist? Es gibt zwei Eigenschaften:

1. Jeder Zustand ist erreichbar: sodass wir erreichen können , q von dem Startzustand s durch folgende w ; in Symbolen: s → w q .$\forall q \in Q \; \exists w \in \Sigma^*$$q$$s$$w$$s \rightarrow_w q$

2. Jedes Paar von Zuständen unterscheiden: mit q ≠ r ∃ w ∈ & Sgr; * , so dass q → w s und r → w t und | { s , t } ∩ F | = 1 (nur einer von$\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$ ist ein Akzeptanzzustand).$s,t$

Beachten Sie, dass die kann in log-Raum (dh berechnet werden L , nur die aktuelle Position verfolgen , wie Sie folgen w zu einem Zeitpunkt ein Brief). Des Weiteren gibt es nur eine endliche Anzahl von Wechseln zwischen ∀ und ∃ so als Folge des Immerman-Szelepcsenyi Satz haben wir , dass das Problem in ist N L .$x \rightarrow_w y$$\mathsf{L}$$w$$\forall$$\exists$$\mathsf{NL}$

Der einfachste Weg , um zu sehen , dass es für schwierig ist , ist zu bemerken , dass Eigentum 1 löst s - t unreachability gerichtet, die das prototypische schwierige Problem ist. Aber selbst wenn Sie nur erreichbare DFAs betrachten, ist das Problem immer noch schwierig (dh Eigenschaft 2 ist N L -hart) und Sie können einen relativ einfachen Beweis in Lemma 2.2 von Cho & Huynh (1992) finden .$\mathsf{NL}$$s$$t$$\mathsf{NL}$

Natürlich habe ich Nicht-Determinismus verwendet, daher ist es ein bisschen hustend, wie es sich von Hopcrofts Algorithmus unterscheidet. Wir wissen jedoch, dass , sodass Sie diese Konstruktionen verwenden können, um einen platzsparenderen Algorithmus als Hopcroft zu erhalten (der naturgemäß n verfolgen muss$\mathsf{NL} \subseteq \mathsf{L}^2$$n$ viele Partitionen im ).