Parametrisierte Komplexität der Einbeziehung regulärer Sprachen

11

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.)EL(E)Σ

Eingabe: Zwei reguläre Ausdrücke und E 2 Frage: Stimmt es, dass L ( E 1 ) L ( E 2 ) ist ?E1E2
L(E1)L(E2)

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 ) C.A1A2E1E2D2A2D2CAPA1D2CL(E1)L(E2)C. Jetzt ist genau dann, wenn es in A P keinen akzeptierenden Pfad gibt .L(E1)L(E2)AP

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 .E2A2D2|E2|E2

Das motiviert meine Frage:

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

[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.)

Florent Foucaud
quelle
4
Es bleibt PSPACE-vollständig, da die Sprachuniversalität (dh E1 = Sigma *) PSPACE-vollständig ist.
Denis
3
Wenn Sie das Quadrieren zulassen, ist das Problem EXPSPACE-vollständig. Die von Ihnen genannten Ergebnisse sind ohne Quadrieren.
Denis
1
Für ist es in konstanter Zeit lösbar. Für E 1 = w für eine feste Zeichenkette w ist es in Polynomzeit lösbar. Für E 1 = Σ * ist PSPACE-vollständig. Gibt es ein E 1, so dass das Problem N P -vollständig ist? E1=E1=wwE1=ΣE1NP
Michael Wehar
2
OK danke! @Denis, bitte verwandle es in eine Antwort (mit einer Referenz), und ich werde es akzeptieren!
Florent Foucaud
3
@ MichaelWehar: Einige coNP-vollständige Fälle werden hier bewiesen ( doi.org/10.1137/080743457 ), aber sie sind nicht für feste Sprachen (sondern für sehr eingeschränkte Sprachklassen )
Florent Foucaud

Antworten:

14

E1E1=Σ

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Σp(n)wΣMeMw

LM$C0$C1$$Cf$CiMp(n)C0wCfCiCi+1MLMM

eΣ=Σ{$}eLMLMee1+e2++ekei

e1=(Σ)$(Σ<p(n)+Σ>p(n))$(Σ)
Cip(n)CiCi+1CiCi+1t(Σ)p(n)tttM
L(e)(Σ) if and only if LM 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.

E1

(Σ)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.

Denis
quelle
Wow, vielen Dank für das Teilen der Referenzen! Das ist ordentlich !! :)
Michael Wehar
2
Ein Kollege von mir hat mich auf die folgende Umfrage hingewiesen, die sich mit dieser Art von regulären Sprach- und Automatenproblemen befasst und weitere nützliche Referenzen enthält: sciencedirect.com/science/article/pii/S0890540110001999
Florent Foucaud