Return to Answer

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. You can also reduce from other PSPACE-complete problems such as TQBF.

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.

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.

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$ 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. You can also reduce from other PSPACE-complete problems such as TQBF.

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.

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. You can also reduce from other PSPACE-complete problems such as TQBF.

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.

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$ 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. You can also reduce from other PSPACE-complete problems such as TQBF.

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 question.

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.RosenkrantzThomas 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.

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$ 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. You can also reduce from other PSPACE-complete problems such as TQBF.

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.