Untergrenze für NFA, die 3-Buchstaben-Sprache akzeptiert

8

Im Zusammenhang mit einer kürzlich gestellten Frage ( Grenzen der Größe des kleinsten NFA für L_k-different ) fragte Noam Nisan nach einer Methode, um eine bessere Untergrenze für die Größe eines NFA anzugeben, als dies aus den Grenzen der Kommunikationskomplexität hervorgeht. Was folgt, ist eine spezielle Version dieses Problems.

Angenommen, L ist eine Sprache über einem Alphabet mit n Buchstaben, dessen Wörter alle die Länge 3 . Bezeichnen Sie die Größe der kleinsten NFA, die akzeptiert, Lmit NFA(L) . Definieren Sie eine n×n2 -Matrix M als M(a;bc)=1 wenn abcL und ansonsten 0 . Bezeichnen Sie die minimale Anzahl von 1 Submatrizen (Submatrix, die nur 1 enthält1's) , die alle die 1 ist in der Matrix M durch COV(M) . ( log(COV(M)) ist also die nicht deterministische Kommunikationskomplexität von M ) Es ist leicht zu erkennen, dass NFA(L)COV(M) . Wenn wir in ähnlicher Weise eine Matrix N als N(ab;c)=1 wennabcL und ansonsten0 , dann haben wir auchNFA(L)COV(N) .

Gibt es ein L für das NFA(L)>COV(M)+COV(N)?

Durch welche Funktion von COV(M) und COV(N) können wir NFA(L)?

domotorp
quelle

Antworten:

12

Die Grenzen ...

Wir haben tatsächlich , siehe Satz 4 in (Gruber & Holzer 2006). Für eine Obergrenze haben wir 2 C o v ( M ) + C o v ( N )D F A ( L ) N F A ( L ) , siehe Satz 11 in derselben Veröffentlichung. NFA(L)Cov(M)+Cov(N)2Cov(M)+Cov(N)DFA(L)NFA(L)

... kann nicht wesentlich verbessert werden

Zwischen und N F A ( L ) kann eine subexponentielle Lücke bestehen . Das folgende Beispiel und der Beweis der Lücke ist eine Anpassung eines ähnlichen Beispiels, das die Einschränkungen von 2-Parteien-Protokollen zum Nachweis von Untergrenzen für die Komplexität nichtdeterministischer Zustände aus (Hromkovič et al. 2009) veranschaulicht:Cov(M)+Cov(N)NFA(L)

Wir verwenden das Alphabet . Sei L = {[n]={1,2,,n} .L={xyz[n]3x=yxz}

Wir kümmern uns zuerst um . Beachten Sie, dass , wenn w = x y z mit y = z , dann w L : Bei x = y , w L und im Fall x y , wir haben auch x z und damit w L . Auch wenn w die Form x y z mit y z hat , dannCov(M)w=xyzy=zwLx=ywLxyxzwLwxyzyzwLxzL=LLL={xyz[n]3y=z}L={xyz[n]3yzxz}

Betrachten Sie nun die zweigeteilten Graphen mit , , sowie mit , , und . Dann führt eine biclique Kantenabdeckung für den Graphen zu einer Abdeckung von mit monochromatischen Submatrizen,G=(U,V,E)U=[n]V={yz[n]2y=z}E=U×VG=(U,V,E)U=[n]V={yz[n]2yz}E={(x,yz)xz}G=(UU,VV,EE)GM1

Ein einfacher Kernelisierungstrick zum Berechnen einer Biclique-Kantenabdeckung für besteht darin, die Zwillingsscheitelpunkte von in Äquivalenzklassen einzuteilen. Dann machen wir dasselbe im resultierenden Graphen für die Zwillingsscheitelpunkte von . Zwillingsscheitelpunkte sind solche mit identischer Nachbarschaft. Dieser Schritt ändert nicht die Mindestanzahl von Bicliques, die erforderlich sind, um alle Kanten im jeweiligen Diagramm abzudecken.GUV

Der Kernelisierungsschritt reduziert zu einem Graphen mit zwei Eckpunkten und einer einzelnen Kante. Somit können die Kanten von mit einem einzigen Fahrrad bedeckt werden. Anwenden der Problemkern Schritt eine Ausbeuten crown Graphen auf Scheitelpunkte , deren bipartite Dimension (die minimale biclique Randabdeckung Nummer) bekannt sein , wobei die inverse Funktion des mittleren Binomialkoeffizient ist ( De Caen et al. 1981). Beachten Sie, dass . Somit wird die Dimension des bipartite ist , die gleich ist .GGG2nσ(n)σσ(n)=O(logn)G1+σ(n)Cov(M)

Betrachten Sie nun . Beachten Sie, dass , wenn mit , dann . Wenn , dann iff . Wir können also mit und . Fast das gleiche Argument wie oben ergibt .Cov(N)w=xyzx=ywLxyxLxzL=LLL={xyz[n]3x=y}L={xyz[n]3xyxz}Cov(N)=1+σ(n)

Es bleibt eine Untergrenze für die nichtdeterministische Zustandskomplexität von . Beachten Sie, dass alle Wörter der Form mit . für jedes dieser Wörter eine akzeptierende Berechnung einer minimalen NFA fest, die akzeptiert . Es sei der Zustand, der nach dem Lesen des Präfixes , und der Zustand, der nach dem Lesen des Präfixes des Eingabeworts . Dann müssen alle Paare unterschiedlich sein. Aus Gründen des Widerspruchs sei für einigeLLxxxx[n]xxxLpxxqxxxxxx(px,qx)(px,qx)=(py,qy)xy. Dann können wir eine akzeptierende Berechnung auf Eingabe konstruieren , derart , dass der NFA im Zustand nach dem Lesen des Präfix , und in Zustand nach dem Präfix Lesen . Aber die Zeichenfolge ist nicht in . Für die Zustandsmenge der NFA zeigt dies, dass . Somit erhalten wir für großes eine subexponentielle Trennung zwischen und(die nichtdeterministische Zustandskomplexität von ).xyxpx=qxxqy=qxxyxyxLQ|Q|2nnCov(M)+Cov(N)|Q|L

Verweise

Hermann Gruber
quelle
1
Nett, danke! Jetzt habe ich dich zurückgezahlt;)
Domotorp