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