DFA-Schnittmenge im subquadratischen Raum?

25

Der Schnittpunkt zweier (minimaler) DFAs mit n Zuständen kann unter Verwendung von O (n 2 ) Zeit und Raum berechnet werden . Dies ist im Allgemeinen optimal, da der resultierende (minimale) DFA n 2 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.

Rasmus Pagh
quelle
3
Ähm ... wenn zwei DFAs mit n Zuständen azyklisch sind, akzeptiert jeder nur eine endliche Menge von Wörtern mit einer Länge von höchstens n. In diesem Fall ist der Schnittpunkt nur der Schnittpunkt der beiden markierten Übergangsgraphen, die n Zustände und haben kann in linearer Zeit und Raum berechnet werden. Oder vermisse ich etwas?
Joshua Grochow
4
Ja, azyklische DFAs akzeptieren nur eine begrenzte Anzahl von Wörtern. Es gibt jedoch Beispiele für azyklische DFAs, deren Schnittmenge die Größe n ^ 2 hat. Denken Sie beispielsweise an einen DFA, der Zeichenfolgen der Form AABC akzeptiert (wobei ABC Zeichenfolgen der Länge k sind), und an einen, der Zeichenfolgen der Form ABCC akzeptiert.
Rasmus Pagh
1
retagging: cs.cc ist eine arxiv-Bezeichnung, daher benötigen die angegebenen Tags nicht das cs.cc-Präfix.
Suresh Venkat

Antworten:

15

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-O(log2n) Raum ( log 2 n ) berechnet werden.kk

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 OAi=(Qi,Σi,δi,zi,Fi)i[k])kA1,,AkL(A1)L(Ak)( log 2 n ) Leerzeichen. Wir beweisen zunächst einige technische Ergebnisse.O(log2n)

Definition 1 : Let q , r zwei Zustände dann q r iff w & egr ; & Sgr; * , q . w F r . w Fq,rqrwΣq.wFr.wF

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 .Aq=(q1,,qk)r=(r1,,rk)A

Lemma 1 : Entscheiden, ob q r in NL ist.qr

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 iF i istwΣq.wr.wqi.w,ri.wi[k]qi [ k ] . Es kann gezeigt werden, dass q r die Existenz eines w mit Polygröße impliziert.qiFii[k]q≢rw

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 ] ).ziqii[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 .As(1)s(i)s(i1)c(q)iqs(i)

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

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önnenkj0qqqjqj=iqs(j)DSPACE ( log 2 n ) , hiermit ist der Beweis abgeschlossen.NLDSPACE(log2n)

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

Theorem : Die Minimierung von A kann im O- Raum ( log 2 n ) erfolgen .AO(log2n)

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 , wobei1m|Q0||Q1|is(i)A=(Q,Σ,δ,z,F)

  • Q ' = { s ( i ) : i [ m ] } ;Q={s(i):i[m]}
  • F ' = { q Q ' : q iF ii [ k ] } ;F={qQ:qiFii[k]}
  • z ' = s ( c ( q ) ) wobei q = ( z 0 , ... , z k ) .z=s(c(q))q=(z0,,zk)

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 'δi[m],aΣqs(i).a(s(i),a,s(c(q)))O(log2n)Aist minimal und L ( A ' ) = L ( A ) .L(A)=L(A)

Michael Blondin
quelle
3
Netter Algorithmus! Hier ist eine etwas andere Sichtweise auf diesen Algorithmus. Der Kern besteht darin, dass die Zustandsminimierung eines beliebigen DFA in Polynomzeit und O ( log 2 n ) -Raum durchgeführt werden kann. Danach ist es einfach, einen DFA zu konstruieren, der den Schnittpunkt im logarithmischen Raum darstellt (daher in Polynomzeit und O- Raum ( log 2 n ) ), und wir können zwei Funktionen zusammensetzen, die in Polynomzeit und O- Raum ( log 2 n ) berechenbar sind (In ähnlicher Weise wie bei der Komposition zweier logarithmischer Raumreduktionen), wobei der gesamte Algorithmus in Polynomzeit und O erhalten wirdO(log2n)O(log2n)O(log2n)( log 2 n ) Leerzeichen. O(log2n)
Tsuyoshi Ito
2
Ich habe gerade diese Antwort gesehen ... Ich verstehe nicht, warum der Algorithmus gleichzeitig in Polytime und O ( log 2 n ) ausgeführt wird. Ja, N L P D S P A C E [ log 2 n ] , aber es ist nicht bekannt, ob N L T I S P [ n O ( 1 ) , log 2 n ] - das heißt, wir können Wenn ein Algorithmus in polytime ausgeführt wird, können wir einen anderen Algorithmus ausführenO(log2n)NLPDSPACE[log2n]NLTISP[nO(1),log2n]O ( log 2 n ) Raum, aber ich weiß nicht, wie ich N L Probleme in polytime und O ( log 2 n ) Raum mit einem einzigen Algorithmuslösenkann. O(log2n)NLO(log2n)
Ryan Williams
Du hast recht, ich weiß auch nicht wie. Ich habe dies vor langer Zeit gepostet, daher bin ich mir nicht sicher, warum ich es so geschrieben habe, aber vielleicht meinte ich "Polynomial Time oder O (log² n)". Ich werde es bearbeiten, weil es irreführend ist. Vielen Dank!
Michael Blondin
14

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.

Andy Drucker
quelle
1
und was ist mit Untergrenzen?
Marcos Villagra
1
Nur um die Fragen zu klären: Ich verbringe gerne O (n ^ 2) Zeit (oder vielleicht sogar n ^ O (1) Zeit), um den gebundenen Raum zu verbessern.
Rasmus Pagh
13

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.

Ryan Williams
quelle
Danke für diesen Hinweis. Ich vermute, dass dies möglicherweise zu einem n ^ Omega (1) -Unterraum führen könnte, der abgesehen von der Eingabe für den zusätzlichen Speicherplatz erforderlich ist. Aber könnte es möglicherweise zu einer superlinearen Untergrenze des Raums führen?
Rasmus Pagh
1
@ user124864 Bei k DFAs mit jeweils n Zuständen hat der Produktautomat n k Zustände. Nun gibt es zwei Tricks, mit denen Sie die Größe reduzieren können. Das erste ist, dass Sie nur die erreichbare Komponente des Produktdiagramms berücksichtigen. Zweitens können Sie den Produkt-DFA minimieren. Letztendlich ist es schwierig herauszufinden, welche Sprache von diesem Produktautomaten erkannt wird. knnk
Michael Wehar
1
@ user124864 Schon der Versuch, festzustellen, ob das Produkt DFA eine nicht leere Sprache erkennt, ist schwierig. Dies ist das Problem der Nicht-Leere an der Kreuzung. Mit schwer meine ich, dass es in einem starken Sinne X N L vollständig ist. XNL
Michael Wehar
1
@ user124864 Wenn Sie es in weniger als n k Zeit lösen können , erhalten wir schnellere Algorithmen für PSPACE-vollständige Probleme. Es ist nicht lösbar in o ( 1 ) binary k log ( n ) nicht deterministischem Binärraum. Es ist nicht bekannt, ob wir es in weniger als k 2 log 2 ( n ) deterministischem Binärraum lösen können. Es ist nicht bekannt, ob wir es in simultaner deterministischer Polynomzeit und f ( k ) log 2 ( n ) binärem Raum für irgendeine Funktion lösen könnennko(1)klog(n)k2log2(n)f(k)log2(n)f (dies würde den Satz von Savitch verbessern). f
Michael Wehar
1
@ user124864 Hinweis: Wir haben beide der folgenden Möglichkeiten. (1) Beating n k Zeit impliziert determinis schneller determinis Algorithmen für PSPACE vollständige Probleme und (2) Schlagen n k Zeit impliziert nicht-deterministisch schneller nicht-deterministische Algorithmen für PSPACE vollständige Probleme. nknk
Michael Wehar
7

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 ) verwendet.ABL(A)L(B)Θ(|A||B|) O(n2)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 inn , 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.1iniaiAB

Michael Blondin
quelle
1
Ja, ich interessiere mich für den Minimalautomaten oder zumindest für einen ähnlich großen Automaten. Vielen Dank für die Hinweise auf unäre DFAs. Dies scheint jedoch für den allgemeinen Fall nicht viel zu helfen.
Rasmus Pagh