# For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

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

• 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 May 12 '16 at 9:17

• 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$);
• 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 May 12 '16 at 20:53