<p>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^*$.</p>

<p>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:</p>

<hr>

<p>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$.</p>

<p>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$.</p>

<p>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^{&lt;p(n)}+\Sigma^{&gt;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.</p>

<hr>

<p>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 <a href="https://www.sciencedirect.com/science/article/pii/S0022000076800384?via%3Dihub" rel="noreferrer">this paper</a> [1] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in <a href="https://cstheory.stackexchange.com/a/34739/8953">this answer</a> (there does exist NP-complete cases). </p>

<p>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.</p>

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

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

CC BY-SA 3.0
2018-02-24T01:21:33.917Z
Wow, thank you very much for sharing the references!!  This is neat!!  :)
Michael Wehar
CC BY-SA 3.0
2018-02-25T11:26:30.403Z
A colleague of mine pointed me to the following survey that deals with this type of regular language and automata problems, and contains further useful references: https://www.sciencedirect.com/science/article/pii/S0890540110001999
Florent Foucaud
CC BY-SA 3.0
2018-02-23T12:37:16.230Z
2018-03-02T13:45:43.247Z
2018-03-02T13:45:43.247Z
Denis
<p>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.)</p>

<p><em>Input:</em> Two regular expressions $E_1$ and $E_2$<br>
<em>Question:</em> Is it true that $L(E_1)\subseteq L(E_2)$?</p>

<p>REGULAR LANGUAGE INCLUSION is known to be PSPACE-complete [1].</p>

<p>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$. </p>

<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$.</p>

<p>This motivates my question:</p>

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

<p>[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.</p>

<p><em>Remark:</em> 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.)</p>

CC BY-SA 3.0
2018-02-22T15:57:23.480Z
It remains PSPACE-complete, as language universality (i.e. E1=Sigma*) is PSPACE-complete.
Denis
CC BY-SA 3.0
2018-02-22T15:59:57.930Z
Btw allowing squaring makes the problem EXPSPACE-complete, the results you mentioned are without squaring.
Denis
CC BY-SA 3.0
2018-02-22T23:05:50.243Z
For $E_1 = \emptyset$, it is solvable in constant time.  For $E_1 = w$ for a fixed string $w$, it is solvable in polynomial time.  For $E_1 = \Sigma^{*}$ it is PSPACE-complete.  Does there exist an $E_1$ such that the problem is $NP$-complete?
Michael Wehar
CC BY-SA 3.0
2018-02-23T10:04:29.987Z
OK, thanks! @Denis, please turn it into an answer (with a reference), and I'll accept it!
Florent Foucaud
CC BY-SA 3.0
2018-02-23T12:05:09.353Z
@MichaelWehar: Some coNP-complete cases are proved here, (https://doi.org/10.1137/080743457) but they are not for *fixed* languages (but for very restricted *classes* of languages)
Florent Foucaud
CC BY-SA 3.0
2018-02-24T01:24:18.110Z
@FlorentFoucaud Thank you very much for sharing!!  I think this is quite neat and Denis's answer contains some more info on the fixed case.  :)
Michael Wehar
<cc.complexity-theory><reference-request><regular-language><parameterized-complexity><regular-expressions>
Parameterized complexity of inclusion of regular languages
Florent Foucaud
# Parameterized complexity of inclusion of regular languages

(Asked by: username_0 on 2018-02-22)

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

**Tags:** cc.complexity-theory, reference-request, regular-language, parameterized-complexity, regular-expressions
> **Comments:**
> **username_1**: It remains PSPACE-complete, as language universality (i.e. E1=Sigma*) is PSPACE-complete.  
> **username_1**: Btw allowing squaring makes the problem EXPSPACE-complete, the results you mentioned are without squaring.  
> **username_2**: For $E_1 = \emptyset$, it is solvable in constant time.  For $E_1 = w$ for a fixed string $w$, it is solvable in polynomial time.  For $E_1 = \Sigma^{*}$ it is PSPACE-complete.  Does there exist an $E_1$ such that the problem is $NP$-complete?  
> **username_0**: OK, thanks! @Denis, please turn it into an answer (with a reference), and I'll accept it!  
> **username_0**: @MichaelWehar: Some coNP-complete cases are proved here, (https://doi.org/10.1137/080743457) but they are not for *fixed* languages (but for very restricted *classes* of languages)  
> **username_2**: @FlorentFoucaud Thank you very much for sharing!!  I think this is quite neat and Denis's answer contains some more info on the fixed case.  :)  

---

## 1 answers

### Answer by username_1 on 2018-02-23. Score: 17 | Accepted 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')^\*$$ 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](https://www.sciencedirect.com/science/article/pii/S0022000076800384?via%3Dihub) [1] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in [this answer](https://cstheory.stackexchange.com/a/34739/8953) (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.

> **Comments:**
> **username_2**: Wow, thank you very much for sharing the references!!  This is neat!!  :)  
> **username_0**: A colleague of mine pointed me to the following survey that deals with this type of regular language and automata problems, and contains further useful references: https://www.sciencedirect.com/science/article/pii/S0890540110001999  

---

