Klassen von NFAs, die effiziente Teilmengenprüfungen oder eindeutige Konvertierungen ermöglichen

Ich recherchiere über NFAs und Inklusionsprobleme mit ihnen. Ich weiß, dass im Allgemeinen die Einschlussprobleme und die Konvertierung in eine eindeutige NFA beide PSPACE-vollständig sind.

Ich frage mich, gibt es Unterklassen von NFA, für die diese effizient entschieden werden können? Insbesondere akzeptieren die NFAs, die ich betrachte, eine endliche Sprache, in der alle Wörter den gleichen Parikh-Vektor haben.

Hier sind drei Refs, die hilfreich sein können.

• Effiziente Inklusionstests für einfache Klassen eindeutiger Autome$\omega$ Dimitri Isaaka, Christof Lodinga

Wir zeigen, dass die Spracheinbeziehung für Sprachen mit unendlichen Wörtern, die durch nicht deterministische Automaten definiert sind, in Polynomzeit getestet werden kann, wenn die Automaten eindeutig sind und einfache Akzeptanzbedingungen haben, nämlich Sicherheits- oder Erreichbarkeitsbedingungen. Ein Automat mit Sicherheitsbedingung akzeptiert ein unendliches Wort, wenn es einen Lauf gibt, der niemals einen verbotenen Zustand besucht, und ein Automat mit Erreichbarkeitsbedingung akzeptiert ein unendliches Wort, wenn es einen Lauf gibt, der mindestens einmal einen akzeptierenden Zustand besucht.

diese zweite ref indirektere & würden auf einer Zuordnung zwischen NFAs und verlassen Baumautomaten .

• Antichain-basierte Universalitäts- und Inklusionstests an nichtdeterministischen endlichen Baumautomaten Ahmed Bouajjani, Peter Habermehl, Lukas Hol´ık, Tayssir Touili ​​und Tomas Vojnar

Wir zeigen die deutlich verbesserte Effizienz dieses Frameworks durch eine Reihe von Experimenten mit der Überprüfung verschiedener Programme über dynamisch verknüpfte baumförmige Datenstrukturen

Der obige Verweis zitiert auch Folgendes:

• Antichains: Ein neuer Algorithmus zur Überprüfung der Universalität endlicher Automaten, M. De Wulf, L. Doyen, TA Henzinger und JF Raskin

Wir zeigen, dass in den schwierigen Fällen dieses Wahrscheinlichkeitsmodells der Antichain-Algorithmus den Standard um mehrere Größenordnungen übertrifft. Wir zeigen auch, wie Variationen der Antichain-Methode zur Lösung des Spracheinschlussproblems für nichtdeterministische endliche Automaten verwendet werden können ...

Als negatives Beispiel wird in diesem Artikel von Kozen gezeigt, dass bei gegebenen DFAs entschieden wird, ob PSPACE-vollständig ist (a direktes Ergebnis von Lemma 3.2.3 in der Arbeit).$A_1,...,A_n$$\bigcup_{i=1}^n L(A_i)=\Sigma^*$

Somit ist die Entscheidung über die Eindämmung selbst für endlich mehrdeutige NFAs PSPACE-vollständig.

Dies bedeutet zwar nicht, dass Ihr Fall nicht effizient entschieden werden kann, gibt jedoch Hinweise darauf, dass dies möglicherweise nicht der Fall ist.