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

Question

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

Answer 1

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)