Es sei zwei reguläre Sprachen, die von den NFAs als Eingabe gegeben werden.
Angenommen, wir möchten überprüfen, ob . Dies kann natürlich durch einen quadratischen Algorithmus geschehen, der den Produktautomaten von berechnet , aber ich habe mich gefragt, ob etwas Effizienteres bekannt ist.
Gibt es einen -Algorithmus, um zu entscheiden, ob ? Was ist der schnellste bekannte Algorithmus?
Antworten:
Einfache Antwort : Wenn es einen effizienteren Algorithmus gibt, der für einige δ < 2 in der -Zeit abläuft , würde die Hypothese der starken Exponentialzeit widerlegt.O(nδ) δ<2
Wir werden einen stärkeren Satz beweisen und dann wird die einfache Antwort folgen.
Theorem : Wenn wir die Kreuzung nicht Leere Problem für zwei DFA in lösen können Zeit, dann jedes Problem , das nicht-determinis lösbare Verwendung von nur n Speicherbits ist deterministisch auflösbar in p o l y ( n ) ⋅ 2 ( δ n / 2 ) Zeit.O(nδ) poly(n)⋅2(δn/2)
Begründung : Nehmen wir an, wir können die Nicht-Leerheit von Kreuzungen für zwei DFAs in -Zeit lösen . Es sei eine nicht deterministische Turingmaschine M mit einem Nur-Lese-Eingabeband und einem Lese- / Schreib-Binär-Arbeitsband gegeben. Es sei eine Eingabezeichenfolge x der Länge n gegeben. Angenommen, M greift nicht auf mehr als n Speicherbits auf dem binären Arbeitsband zu.O(nδ)
Eine Berechnung von M am Eingang x kann durch eine endliche Liste von Konfigurationen dargestellt werden. Jede Konfiguration besteht aus einem Status, einer Position auf dem Eingabeband, einer Position auf dem Arbeitsband und bis zu n Speicherbits, die das Arbeitsband darstellen.
Stellen Sie sich nun vor, dass das Arbeitsband in zwei Hälften geteilt wurde. Mit anderen Worten, wir haben einen linken Abschnitt von Zellen und ein rechter Abschnitt vonnn2 Zellen. Jede Konfiguration kann in ein linkes und ein rechtes Stück unterteilt werden. Das linke Stück besteht aus dem Zustand, der Position auf dem Eingabeband, der Position auf dem Arbeitsband und demnn2 Bits vom linken Abschnitt. Das rechte Stück besteht aus dem Zustand, der Position auf dem Eingangsband, der Position auf dem Arbeitsband und demnn2 Bits aus dem rechten Abschnitt.n2
Jetzt bauen wir einen DFA dessen Zustände linke Teile sind, und einen DFA D 2, dessen Zustände rechte Teile sind. Die alphabetischen Zeichen sind Anweisungen, die angeben, in welchen Zustand sich die Bandköpfe bewegen sollen und wie die aktive Zelle des Arbeitsbands manipuliert werden soll.D1 D2
Die Idee ist, dass und D 2 eine Liste von Befehlen einlesen, die einer Berechnung von M am Eingang x entsprechen, und gemeinsam überprüfen, ob sie gültig und akzeptabel sind. Sowohl D 1 als auch D 2 stimmen immer darin überein, wo sich die Bandköpfe befinden, da diese Informationen in ihren Eingabezeichen enthalten sind. Daher kann D 1 überprüft werden, ob die Anweisung geeignet ist, wenn sich die Arbeitsbandposition im linken Teil befindet, und D 2 überprüft werden, wenn sich das rechte Teil befindet.D1 D2 D1 D2 D1 D2
Insgesamt gibt es höchstens Zuständen für jede DFA und höchstens p o l y ( n ) eindeutige alphabetische Zeichen.poly(n)⋅2n/2 poly(n)
Durch die anfängliche Annahme folgt, dass wir nicht-Kreuzung Leere für die beiden DFA in lösen der Zeit.poly(n)⋅2(δn/2)
Dies könnte hilfreich sein: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/
Kommentare, Korrekturen, Vorschläge und Fragen sind willkommen. :)
quelle