Sparametryzowana złożoność włączenia zwykłych języków

Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu z unii operacji, Kleene-gwiazdkowe i konkatenacji). $E$ $L(E)$ $\Sigma$

Dane wejściowe: dwa wyrażenia regularne i Pytanie: Czy to prawda, że ? $E_1$ $E_2$
$L(E_1)\subseteq L(E_2)$

REGULARNE WŁĄCZANIE JĘZYKA jest znane z funkcji PSPACE-complete [1].

Klasyczny sposób rozwiązać (na PSPACE) jest skonstruować NFAs i związane z i , aby zbudować DFA z , uzupełnienie go do DFA , a wreszcie budowie przecięcia automat z i odpowiadającej przecięciu i $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$ . Obecnie , wtedy i tylko wtedy, gdy nie ma jednostki przejmującej w ścieżka . $L(E_1)\subseteq L(E_2)$ $A_P$

Jeśli się nie mylę, cały proces może odbywać się w czasie wielomianowym, gdy jest ustalony język, ponieważ tylko wykładniczy blow-up pochodzi z przekształcenia w . Co więcej, problemem jest FPT, gdy jest sparametryzowany przez , długość . $E_2$ $A_2$ $D_2$ $|E_2|$ $E_2$

To motywuje moje pytanie:

Pytanie: Kiedy jest wyrażeniem stałym, jaka jest złożoność REGULARNEGO WŁĄCZENIA JĘZYKA? Czy pozostaje kompletny z PSPACE? $E_1$

[1] LJ Stockmeyer i AR Meyer. Problemy ze słowami wymagające czasu wykładniczego: raport wstępny. Materiały z piątego dorocznego sympozjum ACM na temat teorii obliczeń, STOC '73, s. 1-9.

Uwaga: Ponieważ nie jestem ekspertem w tej dziedzinie, uważam [1] (i powiązane dokumenty tamtych czasów) za dość nieczytelne i nie mogłem znaleźć innego dowodu kompletności PSPACE - żadnego wskaźnika do współczesnego dowodu, takiego jak książka, jest bardzo mile widziana! Ponadto wydaje się, że autorzy zezwalają na wyrównywanie wyrażeń regularnych, co, jak sądzę, jest obecnie raczej niestandardowe).

cc.complexity-theory reference-request regular-language parameterized-complexity regular-expressions Florent Foucaud
źródło

Pozostaje kompletny z PSPACE, ponieważ uniwersalność językowa (tj. E1 = Sigma *) jest kompletna z PSPACE.

Denis

Btw zezwalając na kwadraty sprawia, że problem EXPSPACE jest kompletny, a wyniki, o których wspomniałeś, nie są kwadratami.

Denis

Dla

można go rozwiązać w stałym czasie. Dla

dla ustalonego ciągu

jest on rozwiązywalny w czasie wielomianowym. Dla

jest on kompletny z PSPACE. Czy istnieje takie

takie, że problem jest

-Complete?

E_{1} = \emptyset

$E_1 = \emptyset$

E_{1} = w

$E_1 = w$

w

$w$

E_{1} = Σ^{*}

$E_1 = \Sigma^{*}$

E_{1}

$E_1$

N P

$NP$

Michael Wehar

Ok dzięki! @Denis, proszę, zmień to w odpowiedź (z odniesieniem), a ja to zaakceptuję!

Florent Foucaud

@MichaelWehar: Niektóre przypadki kompletnych koNP są tutaj udowodnione ( doi.org/10.1137/080743457 ), ale nie są dla ustalonych języków (ale dla bardzo ograniczonych klas języków)

Florent Foucaud

$E_1$ $E_1=\Sigma^*$

Naprawdę trudno jest znaleźć nowoczesny czytelny dowód twardości PSPACE dla uniwersalności wyrażeń regularnych, ponieważ jest to obecnie uważane za folklor. Oto szybki schemat próbny, który pozwala odbudować dowód:

$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} = (Σ^{'})^{*} $ (Σ^{< p (n)} + Σ^{> p (n)}) $ (Σ^{'})^{*}

$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$

C_{i}

$C_i$

p (n)

$p(n)$

C_{i}

$C_i$

C_{i + 1}

$C_{i+1}$

C_{i}

$C_i$

C_{i + 1}

$C_{i+1}$

t (Σ^{'})^{p (n)} t^{'}

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

t

$t$

t^{'}

$t'$

M

$M$

L (e) \neq (Σ^{'})^{*} if and only if L_{M} \neq \emptyset if and only if M accepts w

$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$ dlatego zredukowaliśmy (wielomianowo) dowolny problem PSPACE do uniwersalności wyrażeń regularnych. Pominąłem kilka szczegółów, ale powinno to pozwolić na zbudowanie pełnego dowodu.

$E_1$

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

[1] O równoważności, ograniczeniu i problemach dotyczących zwykłych i bezkontekstowych języków Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Journal of Computer and System Sciences. Tom 12, wydanie 2, kwiecień 1976 r., Strony 222–268

[2] Problem równoważności wyrażeń regularnych z kwadratem wymaga przestrzeni wykładniczej . Meyer, AR i L. Stockmeyer. 13. sympozjum IEEE na temat teorii przełączania i automatyki, październik 1972 r., S. 125–129.

Denis
źródło

Wow, bardzo dziękuję za udostępnienie referencji !! To jest miłe !! :)

Michael Wehar

Mój kolega wskazał mi na następującą ankietę, która dotyczy tego rodzaju regularnych problemów z językiem i automatami, i zawiera dalsze przydatne odniesienia: sciencedirect.com/science/article/pii/S0890540110001999

Florent Foucaud

Sparametryzowana złożoność włączenia zwykłych języków

Odpowiedzi: