Complexité paramétrée de l'inclusion des langues régulières

Je m'intéresse au problème classique INCLUSION DE LA LANGUE RÉGULIÈRE. Étant donné une expression régulière , nous notons L ( E ) le langage régulier qui lui est associé. (Les expressions régulières sont sur un alphabet fixe Σ , avec les opérations union, Kleene-star et concaténation.)$E$$L(E)$$\Sigma$

Entrée: Deux expressions régulières et E 2 Question: Est-il vrai que L ( E 1 ) ⊆ L ( E 2 ) ?$E_1$$E_2$
$L(E_1)\subseteq L(E_2)$

L'INCLUSION DE LANGUE RÉGULIÈRE est connue pour être PSPACE-complete [1].

La manière classique de le résoudre (dans PSPACE) est de construire les NFA et A 2 associés à E 1 et E 2 , de construire un DFA D 2 à partir de A 2 , de le compléter en DFA D C 2 , et enfin, construire l'automate d'intersection A P à partir de A 1 et D C 2 correspondant à l'intersection de L ( E 1 ) et 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$. Maintenant , si et seulement s'il n'y a pas un chemin acceptant en A P .$L(E_1)\subseteq L(E_2)$$A_P$

Si je ne me trompe pas, tout le processus peut se faire en temps polynomial lorsque est un langage fixe, car la seule explosion exponentielle vient de la transformation de A 2 en D 2 . Encore mieux, le problème est FPT lorsqu'il est paramétré par | E 2 | , la longueur de E 2 .$E_2$$A_2$$D_2$$|E_2|$$E_2$

Cela motive ma question:

Question: Lorsque est une expression fixe, quelle est la complexité de l'INCLUSION DE LA LANGUE RÉGULIÈRE? Reste-t-il complet sur PSPACE?$E_1$

[1] LJ Stockmeyer et AR Meyer. Problèmes de mots nécessitant un temps exponentiel: rapport préliminaire. Actes du cinquième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '73, pp. 1-9.

Remarque: Étant un non-expert dans le domaine, je trouve [1] (et les articles connexes de l'époque) tout à fait illisible, et je n'ai pas pu trouver une autre preuve de l'exhaustivité de PSPACE - aucun pointeur vers une preuve moderne, comme dans un livre, est le bienvenu! De plus, les auteurs semblent autoriser la quadrature dans leurs expressions régulières, ce qui est aujourd'hui plutôt non standard, je crois.)

$E_1$$E_1=\Sigma^*$

Il est en effet difficile de trouver une preuve de dureté PSPACE lisible et moderne pour l'universalité de l'expression régulière, car elle est maintenant considérée comme du folklore. Voici un schéma de preuve rapide qui vous permet de reconstruire la preuve:

---

$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$$ nous avons donc réduit (polynomialement) un problème PSPACE arbitraire à l'universalité d'une expression régulière. J'ai omis quelques détails, mais cela devrait vous permettre de construire une preuve complète.

---

$E_1$

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

[1] Sur l'équivalence, le confinement et les problèmes de couverture pour les langages réguliers et sans contexte Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Journal of Computer and System Sciences. Volume 12, numéro 2, avril 1976, pages 222-268

[2] Le problème d'équivalence pour les expressions régulières avec quadrature nécessite un espace exponentiel . Meyer, AR et L. Stockmeyer. 13th IEEE Symposium on Switching and Automata Theory, octobre 1972, pp.125-129.