<p>This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is</p>

<ul>
<li>in P if $L(\alpha)$ is finite;</li>
<li>coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$ for some $w_1,\ldots, w_k$);</li>
<li>PSPACE-complete otherwise.</li>
</ul>

<p>[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages, Journal of Computer and System Sciences, Volume 12, Issue 2, 1976, Pages 222-268, ISSN 0022-0000, <a href="http://dx.doi.org/10.1016/S0022-0000(76)80038-4">http://dx.doi.org/10.1016/S0022-0000(76)80038-4</a>.
(<a href="http://www.sciencedirect.com/science/article/pii/S0022000076800384">http://www.sciencedirect.com/science/article/pii/S0022000076800384</a>)</p>

CC BY-SA 3.0
2016-05-12T11:59:42.117Z
A comment on the previous answer (I don't have enough rep on this site to comment): I don't think this can be right.  It is a classical result of Meyer-Stockmeyer (Theorem 6.1 of [2]) that universality for unary regular languages is coNP-complete.

[2] L. J. Stockmeyer and A. R. Meyer. 1973. Word problems requiring exponential time(Preliminary Report). In Proceedings of the fifth annual ACM symposium on Theory of computing (STOC '73). ACM, New York, NY, USA, 1-9
David
CC BY-SA 3.0
2016-05-12T20:53:51.683Z
I was confused by your comment because the "previous answer" you referred to has been deleted. But anyway unary languages fall into the "bounded" case of your answer with $k=1$ and $|w_1|=1$.
David Eppstein
CC BY-SA 3.0
2016-05-12T11:52:26.467Z
2016-05-12T11:52:26.467Z
David
<p>It is well known that the following problem is PSPACE-complete:</p>
<blockquote>
<p>Given regular expression <span class="math-container">$\beta$</span>, does <span class="math-container">$L(\beta) = \Sigma^*$</span>?</p>
</blockquote>
<p>What about determining equivalence to other (fixed) regular expressions <span class="math-container">$\alpha$</span>?</p>
<blockquote>
<p>Given regular expression <span class="math-container">$\beta$</span>, does <span class="math-container">$L(\beta) = L(\alpha)$</span>?</p>
</blockquote>
<p>The following is known:</p>
<ul>
<li><p>For <span class="math-container">$\alpha = (0+1)^*$</span>, the problem is PSPACE-complete</p>
</li>
<li><p>For <span class="math-container">$\alpha = \emptyset$</span>, or more generally <span class="math-container">$\alpha$</span> that describes a finite set, the problem is decidable in polynomial time.</p>
</li>
</ul>
<p>It also seems likely to me that the problem is in P if <span class="math-container">$\alpha$</span> is a unary language.</p>
<p>So my questions are:</p>
<blockquote>
<p>For which <span class="math-container">$\alpha$</span> is the above decision problem PSPACE-complete? Is there a complete characterization?</p>
<p>Are there any <span class="math-container">$\alpha$</span> for which the decision problem has some intermediate complexity (like NP-complete)?</p>
</blockquote>

CC BY-SA 3.0
2016-05-12T09:17:46.573Z
What operations are allowed in your regular expressions? Clearly, if you have complement (or rather, symmetric difference), the complexity of the problem is independent of $\alpha$.
Emil Jeřábek
<cc.complexity-theory><automata-theory><regular-expressions><pspace>
For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?
mikero
# For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

(Asked by: username_0 on 2016-05-12)

It is well known that the following problem is PSPACE-complete:

> Given regular expression $\beta$, does $L(\beta) = \Sigma^\*$?

What about determining equivalence to other (fixed) regular expressions $\alpha$?

> Given regular expression $\beta$, does $L(\beta) = L(\alpha)$?

The following is known:

* For $\alpha = (0+1)^\*$, the problem is PSPACE-complete
* For $\alpha = \emptyset$, or more generally $\alpha$ that describes a finite set, the problem is decidable in polynomial time.

It also seems likely to me that the problem is in P if $\alpha$ is a unary language.

So my questions are:

> For which $\alpha$ is the above decision problem PSPACE-complete? Is there a complete characterization?
>
> Are there any $\alpha$ for which the decision problem has some intermediate complexity (like NP-complete)?

**Tags:** cc.complexity-theory, automata-theory, regular-expressions, pspace
> **Comments:**
> **username_1**: What operations are allowed in your regular expressions? Clearly, if you have complement (or rather, symmetric difference), the complexity of the problem is independent of $\alpha$.  

---

## 1 answers

### Answer by username_2 on 2016-05-12. Score: 20 | Accepted answer

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is

* in P if $L(\alpha)$ is finite;
* coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\subseteq w\_1^\*w\_2^\*\ldots w\_k^\*$ for some $w\_1,\ldots, w\_k$);
* PSPACE-complete otherwise.

[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages, Journal of Computer and System Sciences, Volume 12, Issue 2, 1976, Pages 222-268, ISSN 0022-0000, <http://dx.doi.org/10.1016/S0022-0000(76)80038-4>.
(<http://www.sciencedirect.com/science/article/pii/S0022000076800384>)

> **Comments:**
> **username_2**: A comment on the previous answer (I don't have enough rep on this site to comment): I don't think this can be right.  It is a classical result of Meyer-Stockmeyer (Theorem 6.1 of [2]) that universality for unary regular languages is coNP-complete.  [2] L. J. Stockmeyer and A. R. Meyer. 1973. Word problems requiring exponential time(Preliminary Report). In Proceedings of the fifth annual ACM symposium on Theory of computing (STOC '73). ACM, New York, NY, USA, 1-9  
> **username_3**: I was confused by your comment because the "previous answer" you referred to has been deleted. But anyway unary languages fall into the "bounded" case of your answer with $k=1$ and $|w_1|=1$.  

---

