Complejidad parametrizada de inclusión de lenguajes regulares

Estoy interesado en el problema clásico INCLUSIÓN DE IDIOMAS REGULARES. Dada una expresión regular , denotamos por L ( E ) el lenguaje regular asociado a ella. (Las expresiones regulares están en un alfabeto fijo Σ , con la unión de operaciones, Kleene-star y concatenación).$E$$L(E)$$\Sigma$

Entrada: Dos expresiones regulares y E 2 Pregunta: ¿Es cierto que L ( E 1 ) ⊆ L ( E 2 ) ?$E_1$$E_2$
$L(E_1)\subseteq L(E_2)$

Se sabe que la INCLUSIÓN DE LENGUAJE REGULAR es completa para PSPACE [1].

La forma clásica de resolverlo (en PSPACE) es construir los NFA y A 2 asociados a E 1 y E 2 , construir un DFA D 2 a partir de A 2 , complementarlo en un DFA D C 2 , y finalmente, construya el autómata de intersección A P a partir de A 1 y D C 2 correspondiente a la intersección de L ( E 1 ) y 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$. Ahora si y sólo si no hay una trayectoria de aceptación en A P .$L(E_1)\subseteq L(E_2)$$A_P$

Si no me equivoco, todo el proceso se puede hacer en tiempo polinómico cuando es un lenguaje fijo, ya que la única explosión exponencial proviene de transformar A 2 en D 2 . Aún mejor, el problema es FPT cuando está parametrizado por | E 2 | , la longitud de E 2 .$E_2$$A_2$$D_2$$|E_2|$$E_2$

Esto motiva mi pregunta:

Pregunta: Cuando es una expresión fija, ¿cuál es la complejidad de la INCLUSIÓN DE LENGUAJE REGULAR? ¿Sigue siendo PSPACE completo?$E_1$

[1] LJ Stockmeyer y AR Meyer. Problemas verbales que requieren tiempo exponencial: informe preliminar. Actas del quinto simposio anual de ACM sobre teoría de la informática, STOC '73, pp. 1-9.

Observación: al no ser un experto en el campo, encuentro [1] (y documentos relacionados de esa época) bastante ilegible, y no pude encontrar otra prueba de la integridad de PSPACE: ningún indicador de una prueba moderna, como en un libro, es muy bienvenido! Además, los autores parecen permitir la cuadratura en sus expresiones regulares, que hoy en día es bastante no estándar, creo).

$E_1$$E_1=\Sigma^*$

De hecho, es difícil encontrar una moderna prueba de dureza PSPACE legible para la universalidad de la expresión regular, ya que ahora se considera folklore. Aquí hay un esquema de prueba rápida que le permite reconstruir la prueba:

---

$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$$ por lo tanto redujimos (polinomialmente) un problema PSPACE arbitrario a la universalidad de una expresión regular. Dejé algunos detalles, pero esto debería permitirle construir una prueba completa.

---

$E_1$

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

[1] Sobre los problemas de equivalencia, contención y cobertura para los idiomas regulares y libres de contexto Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Revista de Informática y Ciencias del Sistema. Volumen 12, Número 2, abril de 1976, páginas 222-268

[2] El problema de equivalencia para expresiones regulares con cuadrado requiere espacio exponencial . Meyer, AR y L. Stockmeyer. 13º Simposio IEEE sobre Conmutación y Teoría de Autómatas, octubre de 1972, págs. 125–129.