# 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