22
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek May 12 '16 at 9:17
17
$\begingroup$

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)

$\endgroup$
  • 3
    $\begingroup$ A comment on the previous answer (I don't have enough rep on this site to comment): I don't think this can be right. It is a classical result of Meyer-Stockmeyer (Theorem 6.1 of [2]) that universality for unary regular languages is coNP-complete. [2] L. J. Stockmeyer and A. R. Meyer. 1973. Word problems requiring exponential time(Preliminary Report). In Proceedings of the fifth annual ACM symposium on Theory of computing (STOC '73). ACM, New York, NY, USA, 1-9 $\endgroup$ – David May 12 '16 at 11:59
  • 2
    $\begingroup$ 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$. $\endgroup$ – David Eppstein May 12 '16 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.