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

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