Gibt es einen effizienten Test, ob eine NFA eine Teilmenge einer anderen NFA akzeptiert?

Ich weiß also, dass es entscheidend ist , zu testen, ob eine reguläre Sprache $R$ eine Teilmenge der regulären Sprache $S$ ist, da wir beide in DFAs konvertieren, berechnen $R \cap \bar{S}$ und dann testen können, ob diese Sprache leer ist.

Da dies jedoch eine Konvertierung in DFAs erfordert, ist es möglich, dass die DFAs und damit der Testalgorithmus in Bezug auf die Anzahl der Zustände in den Eingangs-NFAs exponentiell sind.

Gibt es einen bekannten Weg, dies in der Polynomzeit zu tun? Hat sich dieses Problem im Allgemeinen als vollständig erwiesen?

$R$ $S$ $R \not \subseteq S$

BEARBEITEN: Dies ist falsch, da es keine Garantie dafür gibt, dass ein solches Wort in der Anzahl der Zustände polynomisch wäre.

algorithms regular-languages automata np-complete decision-problem jmite
quelle

ist das eine theoretische frage oder etwa in der praxis? manchmal kann für eine bestimmte "Verteilung" von Eingaben, die in der Praxis angetroffen werden, ein Pspace-Gesamtproblem in P-Zeit "ausführbar" sein.

vzn

Idealerweise ist es theoretisch, aber die Beweise, an denen ich arbeite, basieren stark auf Computertests, was bedeutet, dass ein schneller Algorithmus definitiv nützlich wäre.

Jmite

Also ja, es gibt einen ziemlich geradlinigen Algorithmus, der einfach den Übergängen für jede der beiden Maschinen parallel folgt und die resultierenden Zustandssätze verfolgt, ähnlich wie beim Standard-Bestimmungsalgorithmus. Ich weiß nicht, ob es irgendwo in der Literatur steht, es ist so einfach, dass ich annehme, dass es so ist. Verwenden Sie bereits einen Algorithmus? Es wäre hilfreich, wenn Sie es zitieren. auch nähere angaben zur art der eingaben wären hilfreich. es hört sich auch so an, als ob Sie feststellen möchten, ob der Schnittpunkt zweier NFAs leer ist. Möchten Sie die Sprache der Kreuzung oder nur Y / N, wenn es nicht leer ist?

vzn

Ich suche nur, ob es leer ist. Die Idee ist, ob , um zu testen, ob . Der Parallelübergangsalgorithmus funktioniert, ich denke, der schwierige Teil ist das Kompliment eines NFA, Sie müssen zuerst in DFA konvertieren. Der Algorithmus, den ich gerade verwende, ist nur Brute-Force, da ich mich nur mit endlichen Sprachen beschäftige.

R - S = {}

$R-S=\{\}$

R \subseteq S

$R \subseteq S$

Jmite

Ich glaube, es gibt eine Möglichkeit, die beiden NFAs zu durchlaufen, ohne sie in einen DFA 1 umzuwandeln, und auch das Komplement eines zu finden. aber ich habe es noch nicht in einem ref gesehen.

vzn

Antworten:

Das Problem bei der Entscheidung über die Spracheinschließung in NFA ist -vollständig. Um dies zu beweisen, ist es leicht aus dem universaility Problem zu reduzieren , für NFAs (Prüfung , ob ) Also, in einer Art und Weise, müssen Sie determinize, aber Sie können tun so on-the-fly. $PSPACE$ $L(A)=\Sigma^*$

Deine Beobachtung über co-NP ist falsch (aber nett). Ein solcher Zeuge kann in der Tat in der Polynomzeit im Zeugen geprüft werden , aber der kürzeste Zeuge selbst kann in der Länge der Eingabe exponentiell sein. Da , ist die Entscheidung über das Nichteinschließen ebenfalls -vollständig. $PSPACE=co-PSPACE$ $PSPACE$

Um Zustand Dinge genauer, zu entscheiden , ob ist in der Größe von (da nur Bedarf ergänzt werden) und in die Größe von . $L(A)\subseteq L(B)$ $PSPACE$ $B$ $B$ $NLOGSPACE$ $A$

Shaull
quelle

Du hast absolut recht. Ich habe mich mit einer bestimmten Klasse von NFAs befasst, bei denen das Gesagte zutrifft, aber es könnte definitiv nicht mit allgemeinen unendlichen NFAs sein. Vielen Dank!

Jmite

Du würdest keinen Verweis auf ein Papier oder ein Lehrbuch haben, das beweist, dass es PSPACE-vollständig ist, oder?

Jmite

Es ist kein sehr detaillierter Beweis, aber ich denke, es wird reichen: wisdom.weizmann.ac.il/~vardi/av/notes/lec4.ps

Shaull

Sie sollten einen Blick auf Jean-François Raskins Artikel Antichain-Algorithmen für endliche Automaten werfen .

In unseren Experimenten erzielte der Einschluss-Test auf Antichain-Basis eine oder zwei Größenordnungen mehr als die "herkömmlichen" Ansätze.

Wenn ich mich richtig erinnere, ist dieser Algorithmus in der libAMoRE ++ Bibliothek implementiert .

Dan
quelle

Eine der besten, umfassendsten und am besten optimierten kostenlosen FSM-Bibliotheken, die online verfügbar sind, ist die AT & T FSM-Bibliothek . Es implementiert "fsmdifference" genau so, wie Sie es beschreiben, und erfordert ein determiniertes epsilon-freies FSM, um den Unterschied zu bewirken . Eine Idee ist es, einen oder beide FSMs zu minimieren, bevor Sie den Unterschied machen, was in einigen Fällen hilfreich sein kann. (Das heißt, das Bestimmen ist nicht dasselbe wie das Minimieren.) Dieses Paket hat auch eine "ungefähre" oder "gierige" Minimierung, die möglicherweise schneller als eine vollständige Minimierung ist.

Bei der Untersuchung ähnlicher Probleme gibt es jedoch meines Erachtens einige Verallgemeinerungen oder Konstruktionen von FSMs, die in der Literatur nicht vorkommen. Sie können dieses Problem lösen, indem sie den Bestimmungsschritt vermeiden, dh eine NFA im Grunde umkehren, ohne eine zusätzliche bestimmte FSM zu erzeugen. Die Idee ist, die NFA-Kanten "parallel" zu durchlaufen und den Satz von Knoten zu verfolgen, die Teil des aktuellen "Superstatus" (Satz von Zuständen) sind, genau wie beim Standard-Bestimmungsalgorithmus. Dann akzeptiert das NFA-Komplement genau dann, wenn die Menge der aktuellen Superstate-Knoten "alle nicht akzeptabel" ist (im Gegensatz zu der bestimmenden Konstruktion, die iff "jedes Akzeptieren" akzeptiert).

Ich habe dies jedoch noch nicht geschrieben und kann es nicht über eine schnelle Online-Suche sehen. Es gibt viele Referenzen, die nahelegen oder implizieren, dass die einzige Möglichkeit, mit dem Komplement einer NFA zu arbeiten, darin besteht, es zu bestimmen.

Hier sind zwei Referenzen in der Nähe, die für einige Ideen nützlich sein könnten. Es würde mich interessieren, von irgendwelchen / anderen zu hören, die "näher" sind. Sie erwähnen, dass Sie an der Programmüberprüfung arbeiten, ein Bereich, in dem das Problem möglicherweise direkter untersucht wird.

[1] Konstruktion der Schnittmenge nichtdeterministischer endlicher Automaten unter Verwendung der Z-Notation Nazir Ahmad Zafar, Nabeel Sabir und Amir Ali

[2] Komplementationskonstruktionen für nichtdeterministische Automaten auf unendlichen Wörtern Orna Kupferman und Moshe Vardi

vzn
quelle