Parameterized complexity of inclusion of regular languages

Question

I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed alphabet $\Sigma$, with the operations union, Kleene-star and concatenation.)

Input: Two regular expressions $E_1$ and $E_2$
Question: Is it true that $L(E_1)\subseteq L(E_2)$?

REGULAR LANGUAGE INCLUSION is known to be PSPACE-complete [1].

The classic way to solve it (in PSPACE) is to construct the NFAs $A_1$ and $A_2$ associated to $E_1$ and $E_2$, to build a DFA $D_2$ from $A_2$, complement it into a DFA $D_2^C$, and finally, build the intersection automaton $A_P$ from $A_1$ and $D_2^C$ corresponding to the intersection of $L(E_1)$ and $L(E_2)^C$. Now $L(E_1)\subseteq L(E_2)$ if and only if there no an accepting path in $A_P$.

If I am not mistaken, the whole process can be done in polynomial time when $E_2$ is a fixed language, since the only exponential blow-up comes from transforming $A_2$ into $D_2$. Even better, the problem is FPT when parameterized by $|E_2|$, the length of $E_2$.

This motivates my question:

Question: When $E_1$ is a fixed expression, what is the complexity of REGULAR LANGUAGE INCLUSION? Does it remain PSPACE-complete?

[1] L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: preliminary report. Proceedings of the fifth annual ACM Symposium on Theory of Computing, STOC '73, pp. 1-9.

Remark: Being a non-expert in the field, I find [1] (and related papers of that time) quite unreadable, and couldn't find another proof of the PSPACE-completeness - any pointer to a modern proof, such as in a book, is very welcome! Also, the authors seem to allow squaring in their regular expressions, which is nowadays rather non-standard, I believe.)

Answer 1

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$.

It is indeed hard to find a modern readable PSPACE-hardness proof for regular expression universality, as it is now considered folklore. Here is a quick proof scheme that allows you to rebuild the proof:

---

Consider a Turing Machine $M$ on alphabet $\Sigma$ using polynomial space $p(n)$, and let $w\in\Sigma^*$ be an input word for $M$. We will build a regular expression $e$ that accepts all words if and only if $M$ has no accepting run on $w$.

Consider the language $L_M$ consisting of words of the form $\$C_0\$ C_1\$\dots\$ C_f\$$, where each $C_i$ is a configuration of $M$ of length exactly $p(n)$, $C_0$ is the initial configuration with $w$ on the tape, $C_f$ is accepting, and each $C_i\to C_{i+1}$ is a valid transition of $M$. A word in $L_M$ describes an accepting run of $M$.

We build $e$ on alphabet $\Sigma'=\Sigma\cup\{\$\}$ such that $e$ accepts exactly words that are not in $L_M$, by looking for a violation of the definition of $L_M$. The expression $e$ will be a big disjunction $e_1+e_2+\dots+e_k$, where each $e_i$ looks for a different kind of violation. For instance $$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$ looks for a violation of the fact that each $C_i$ has size exactly $p(n)$. The most tricky part is guessing a violation between $C_i$ and $C_{i+1}$: the expression can compare a local pattern in $C_i$ and its image in $C_{i+1}$, using $t(\Sigma')^{p(n)}t'$, where $t$ and $t'$ are expressions for local patterns. With this we can guess a violation of the transition function of $M$ on a local pattern, or a violation of the identity outside of this pattern. In the end, we obtain that $$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$$ therefore we reduced (polynomially) an arbitrary PSPACE problem to universality of a regular expression. I left out some details, but this should allow you to build a complete proof.

---

Of course, as pointed out by Michael Wehar in the comments, for others $E_1$ the problem can become simpler. Classifying the complexity of this problem has been studied extensively in this paper [1] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in this answer (there does exist NP-complete cases).

As for your remark on squaring: allowing squaring in regular expressions make the inclusion and universality problem EXPSPACE-complete [2]. Remark that this can be seen in the proof scheme above, since $(\Sigma')^{p(n)}$ can now be expressed with a logarithmic-size expression in $p(n)$ using its binary decomposition, so we can go up to an exponential $p(n)$ while keeping the size of the expression polynomial.

[1] On the equivalence, containment, and covering problems for the regular and context-free languages Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Journal of Computer and System Sciences. Volume 12, Issue 2, April 1976, Pages 222-268

[2] The equivalence problem for regular expressions with squaring requires exponential space. Meyer, A.R. and L. Stockmeyer. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.