Parametrisierte Komplexität der Einbeziehung regulärer Sprachen

Ich interessiere mich für das klassische Problem REGELMÄSSIGE SPRACHEINKLUSION. Bei einem regulären Ausdruck bezeichnen wir mit L ( E ) die damit verbundene reguläre Sprache. (Reguläre Ausdrücke befinden sich in einem festen Alphabet Σ mit der Operations Union, dem Kleene-Stern und der Verkettung.)$E$$L(E)$$\Sigma$

Eingabe: Zwei reguläre Ausdrücke und E 2 Frage: Stimmt es, dass L ( E 1 ) ⊆ L ( E 2 ) ist ?$E_1$$E_2$
$L(E_1)\subseteq L(E_2)$

REGELMÄSSIGE SPRACHEINKLUSION ist bekanntermaßen PSPACE-vollständig [1].

Die klassische Art und Weise , sie zu lösen (in PSPACE) ist der NFAs zu konstruieren und A 2 mit zugeordneten E 1 und E 2 , ein DFA zu bauen D 2 von A 2 , es in einen DFA ergänzt D C 2 , und schließlich, Bauen Sie den Schnittautomaten A P aus A 1 und D C 2 entsprechend dem Schnittpunkt von L ( E 1 ) und L ( E 2 ) $A_1$$A_2$$E_1$$E_2$$D_2$$A_2$$D_2^C$$A_P$$A_1$$D_2^C$$L(E_1)$$L(E_2)^C$. Jetzt ist genau dann, wenn es in A P keinen akzeptierenden Pfad gibt .$L(E_1)\subseteq L(E_2)$$A_P$

Wenn ich mich nicht irre, kann der gesamte Prozess in Polynomzeit durchgeführt werden, wenn eine feste Sprache ist, da die einzige exponentielle Explosion durch die Umwandlung von A 2 in D 2 entsteht . Noch besser ist das Problem FPT, wenn es mit | parametrisiert wird E 2 | die Länge von E 2 .$E_2$$A_2$$D_2$$|E_2|$$E_2$

Das motiviert meine Frage:

Frage: Wenn ein fester Ausdruck ist, wie komplex ist die REGELMÄSSIGE SPRACHEINKLUSION? Bleibt es PSPACE-vollständig?$E_1$

[1] LJ Stockmeyer und AR Meyer. Wortprobleme, die exponentielle Zeit erfordern: vorläufiger Bericht. Vorträge des fünften jährlichen ACM-Symposiums zur Theorie des Rechnens, STOC '73, S. 1-9.

Bemerkung: Als Nicht-Experte auf diesem Gebiet finde ich [1] (und verwandte Artikel dieser Zeit) ziemlich unlesbar und konnte keinen weiteren Beweis für die Vollständigkeit von PSPACE finden - irgendeinen Hinweis auf einen modernen Beweis wie in ein Buch, ist sehr willkommen! Außerdem scheinen die Autoren das Quadrieren in ihren regulären Ausdrücken zuzulassen, was heutzutage meiner Meinung nach eher unüblich ist.)

$E_1$$E_1=\Sigma^*$

Es ist in der Tat schwierig, einen modernen lesbaren PSPACE-Härtebeweis für die Universalität des regulären Ausdrucks zu finden, da er heute als Folklore gilt. Hier ist ein schnelles Proof-Schema, mit dem Sie den Proof neu erstellen können:

---

$M$$\Sigma$$p(n)$$w\in\Sigma^*$$M$$e$$M$$w$

$L_M$$\$C_0\$ C_1\$\dots\$ C_f\$$$C_i$$M$$p(n)$$C_0$$w$$C_f$$C_i\to C_{i+1}$$M$$L_M$$M$

$e$$\Sigma'=\Sigma\cup\{\$\}$$e$$L_M$$L_M$$e$$e_1+e_2+\dots+e_k$$e_i$

$$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$ $C_i$$p(n)$$C_i$$C_{i+1}$$C_i$$C_{i+1}$$t(\Sigma')^{p(n)}t'$$t$$t'$$M$ $$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$$ Daher haben wir (willkürlich) ein beliebiges PSPACE-Problem auf die Universalität eines regulären Ausdrucks reduziert. Ich habe einige Details ausgelassen, aber dies sollte es Ihnen ermöglichen, einen vollständigen Beweis zu erstellen.

---

$E_1$

$(\Sigma')^{p(n)}$$p(n)$$p(n)$

[1] Zur Gleichwertigkeit, Eindämmung und Abdeckung von Problemen für die regulären und kontextfreien Sprachen Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Enzymanski. Zeitschrift für Computer- und Systemwissenschaften. Band 12, Ausgabe 2, April 1976, Seiten 222-268

[2] Das Äquivalenzproblem für reguläre Ausdrücke mit Quadrierung erfordert exponentiellen Raum . Meyer, AR und L. Stockmeyer. 13. IEEE-Symposium über Switching und Automatentheorie, Oktober 1972, S. 125–129.