Skip to main content
1 of 3
mikero
  • 2.8k
  • 23
  • 23

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

mikero
  • 2.8k
  • 23
  • 23