DFA-Schnittmenge im subquadratischen Raum?

Der Schnittpunkt zweier (minimaler) DFAs mit n Zuständen kann unter Verwendung von O (n ² ) Zeit und Raum berechnet werden . Dies ist im Allgemeinen optimal, da der resultierende (minimale) DFA n ² Zustände haben kann. Wenn der resultierende minimale DFA jedoch z-Zustände hat, wobei z = O (n), kann er im Raum n ^2-eps für eine Konstante eps> 0 berechnet werden ? Ein solches Ergebnis würde mich auch für den Sonderfall interessieren, bei dem die Eingabe-DFAs azyklisch sind.

Die Antwort lautet Ja, ohne dass die Größe des Automaten geändert werden muss. Sie kann auch für k DFAs, bei denen k eine Konstante ist, im $O(\log^2 n)$ Raum ( log 2 n ) berechnet werden.$k$$k$

Let A i = ( Q i , Σ i , δ i , z i , F i ) ( i ∈ [ k ] ) sein k DFAs. Wir zeigen , daß, da ⟨ A 1 , ... , A k ⟩ , das Berechnen der minimalen DFA Erkennen L ( A 1 ) ∩ ⋯ ∩ L ( A k ) kann durchgeführt werden in $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$$i \in [k])$$k$$\langle A_1, \ldots, A_k \rangle$$\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$( log 2 n ) Leerzeichen. Wir beweisen zunächst einige technische Ergebnisse.$O(\log^2 n)$

Definition 1 : Let q , r zwei Zustände dann q ≡ r iff ∀ w & egr ; & Sgr; * , q . w ∈ F ⇔ r . w ∈ $q, r$$q \equiv r$$\forall w \in \Sigma^*$$q . w \in F \Leftrightarrow r . w \in F$

Wir betrachten nun den Automaten A , der durch die klassische kartesische Produktkonstruktion gegeben ist. Lassen q = ( q 1 , ... , Q k ) und r = ( r 1 , ... , r k ) Zustände von Be A .$A$$q = (q_1, \ldots, q_k)$$r = (r_1, \ldots, r_k)$$A$

Lemma 1 : Entscheiden, ob q ≡ r in NL ist.$q \equiv r$

Beweis (Skizze): Wir zeigen, dass die Testungleichwertigkeit in NL vorliegt und verwenden NL = coNL. Erraten ein Wort w ∈ & Sigma; * (ein Buchstabe zu der Zeit) , so dass q . w ist ein Endzustand und r . w ist nicht. Dies kann durch Berechnung von q i erreicht werden . w , r i . w im log-Raum für i ∈ [ k ] und unter Verwendung der Tatsache, dass q final ist, wenn q i ∈ F $w \in \Sigma^*$$q . w$$r . w$$q_i . w, r_i . w$$i \in [k]$$q$∀ i ∈ [ k ] . Es kann gezeigt werden, dass q ≢ r die Existenz eines w mit Polygröße impliziert.$q_i \in F_i \, \forall i \in [k]$$q \not\equiv r$$w$

Lemma 2 : Entscheiden, ob q (in) zugänglich ist, ist in NL.$q$

Beweis (Skizze): Errate (Poly-Größe) Pfade von z i zu q i ( i ∈ [ k ] ).$z_i$$q_i$$i \in [k]$

Definition 2 : Betrachten Sie die Zustände von A in lexikographischer Reihenfolge. Definieren Sie s ( 1 ) als den ersten zugänglichen Zustand und s ( i ) als den ersten zugänglichen Zustand nach s ( i - 1 ), der keinem vorherigen Zustand entspricht. Wir definieren c ( q ) als das eindeutige i, so dass q ≡ s ( i ) ist .$A$$s(1)$$s(i)$$s(i-1)$$c(q)$$i$$q \equiv s(i)$

Lemma 3 : s ( i ) kann im O- Raum ( log 2 n ) berechnet werden.$s(i)$$O(\log^2 n)$

Beweis (Skizze): Definition 2 liefert einen Algorithmus. Wir verwenden k Zähler, um über die Zustände zu iterieren. Sei j ← 0 und q der aktuelle Zustand. In jedem Zustand verwenden wir Lemma 2, um zu überprüfen, ob auf q zugegriffen werden kann. Wenn dies der Fall ist, durchlaufen wir alle vorherigen Zustände und überprüfen, ob einer von ihnen q entspricht . Wenn es keine gibt, erhöhen wir j und geben q aus, wenn j = i ist . Andernfalls speichern wir q als s ( j ) und fahren fort. Da wir nur eine konstante Anzahl von Zählern speichern und unsere Tests in NL durchgeführt werden können$k$$j \leftarrow 0$$q$$q$$q$$j$$q$$j = i$$q$$s(j)$⊆ DSPACE ( log 2 n ) , hiermit ist der Beweis abgeschlossen.$\text{NL} \subseteq \text{DSPACE}(\log^2 n)$

Folgerung 1 : c ( q ) kann im O- Raum ( log 2 n ) berechnet werden.$c(q)$$O(\log^2 n)$

Theorem : Die Minimierung von A kann im O- Raum ( log 2 n ) erfolgen .$A$$O(\log^2 n)$

Beweis (Skizze): Sei 1 ≤ m ≤ | Q 0 | ⋯ | Q 1 | sei das größte i, so dass s ( i ) definiert ist (dh die Anzahl der Klassen von ≡ ). Wir geben einen Algorithmus an, der einen Automaten A ' = ( Q ' , Σ , δ ' , z ' , F ' ) ausgibt , wobei$1 \leq m \leq |Q_0| \cdots |Q_1|$$i$$s(i)$$\equiv$$A' = (Q', \Sigma, \delta', z', F')$

• Q ' = { s ( i ) : i ∈ [ m ] } ;$Q' = \lbrace s(i) : i \in [m] \rbrace$
• F ' = { q ≤ Q ' : q i ≤ F i∀ i ∈ [ k ] } ;$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$
• z ' = s ( c ( q ) ) wobei q = ( z 0 , ... , z k ) .$z' = s(c(q))$$q = (z_0, \ldots, z_k)$

Wir zeigen nun, wie man δ ′ berechnet . Für jedes i ∈ [ m ] , ein ∈ & Sigma; , compute q ← s ( i ) . a und Ausgang der Übergang ( s ( i ) , a , s ( c ( q ) ) ) . Nach Lemma 3 und Korollar 1 läuft dieser Algorithmus im O- Raum ( log 2 n ) . Es kann überprüft werden, dass A $\delta'$$i \in [m], a \in \Sigma$$q \leftarrow s(i) . a$$\left(s(i), a, s(c(q))\right)$$O(\log^2 n)$$A'$ist minimal und L ( A ' ) = L ( A ) .$\text{L}(A') = \text{L}(A)$

Dick Lipton und Kollegen haben kürzlich an diesem Problem gearbeitet, und Lipton hat hier darüber gebloggt:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Es sieht so aus, als ob eine bessere Leistung als O (n ^ 2) auch für den ganz speziellen Fall offen ist, bei dem festgestellt wird, ob die DFA-Schnittmenge die leere Sprache definiert.
Der Aufsatz enthält Konsequenzen für die Komplexität, die sich aus einem stark verbesserten Algorithmus ergeben würden, der nicht nur 2 DFAs in der Schnittmenge, sondern auch größere Zahlen verarbeitet.

Wenn Sie k DFAs erhalten (k ist Teil der Eingabe) und wissen möchten, ob ihre Schnittmenge leer ist, ist dieses Problem im Allgemeinen PSPACE-vollständig:

Dexter Kozen: Untere Schranken für natürliche Beweissysteme FOCS 1977: 254-266

Wenn Sie diesen Beweis (und ähnliche Konstruktionen von Lipton und seinen Co-Autoren) sorgfältig studieren, finden Sie möglicherweise eine Art Raumuntergrenze, selbst für festes k.

Bei zwei Automaten A , B , die endliche Sprachen akzeptieren (azyklische Automaten), ist die Zustandskomplexität von L ( A ) ∩ L ( B ) in Θ ( | A | ⋅ | B | ) (1) . Dieses Ergebnis gilt auch für unäre DFAs (nicht unbedingt azyklisch) (2) . Sie scheinen jedoch über den Platz zu sprechen, der für die Berechnung der Schnittmenge zweier Automaten erforderlich ist. Ich verstehe nicht, wie die klassische Konstruktion mit dem kartesischen Produkt O ( n 2$A$$B$$L(A) \cap L(B)$$\Theta(|A| \cdot |B|)$ $O(n^2)$Platz. Sie benötigen lediglich eine konstante Anzahl von Zählern mit logarithmischer Größe. Wenn Sie die Übergangsfunktion für den neuen Status ( q , r ) berechnen , müssen Sie nur die Eingabe scannen, ohne zuvor generierte Daten zu überprüfen.$(q,r)$

Vielleicht möchten Sie den Minimalautomaten ausgeben? Wenn dies der Fall ist, habe ich keine Ahnung, ob es erreicht werden kann. Die staatliche Komplexität der Schnittmenge für endliche Sprachen scheint nicht ermutigend. Unäre DFAs haben jedoch die gleiche Zustandskomplexität, und ich denke, dass dies mit solchen Automaten erreicht werden kann. Mit den Ergebnissen aus (2) können Sie die genaue Größe des Automaten ermitteln, der die Kreuzung erkennt. Diese Größe wird durch die Länge des Schwanzes und des Zyklus beschrieben, daher kann die Übergangsfunktion leicht mit sehr wenig Raum berechnet werden, da die Struktur vollständig durch diese beiden Größen beschrieben wird. Dann müssen Sie nur noch den Satz der Endzustände erzeugen. Sei n die Anzahl der Zustände im resultierenden Automaten, dann für alle 1 ≤ $n$≤ n , Zustand i ist ein Endzustand, wenn a i sowohl von A als auch von B akzeptiert wird. Dieser Test kann mit wenig Platz durchgeführt werden.$1 \leq i \leq n$$i$$a^i$$A$$B$