If the complexity of recognizing whether two regular expressions represent different languages is EXPSPACE-complete, then what can be said for the complexity of recognizing whether two $\omega$-regular expressions represent different languages?

  • $\begingroup$ You make it sound like it's a homework problem; I had just been reading on Buchi automata and wondered about the answer to this question, hence my post here, to which (as you can see I've accepted it as an answer) someone had promptly provided an answer with solid reasoning. $\endgroup$ – Francesco Gramano Mar 23 '15 at 9:29
  • $\begingroup$ No matter the level of a question, we still appreciate context and/or a display of own research or other effort. You could, for instance, have included consequences of both problem being (not) equally hard (is it even decidable of two $\omega$-regular expressions are equivalent?), state where you have looked for an answer (so potential answerers don't have to), sketch a proof attempt for either direction and where you get stuck, and so on. $\endgroup$ – Raphael Mar 23 '15 at 10:15

It's quite easy to reduce the equivalence problem for regular expressions to the equivalence problem for $\omega$-regular expressions, so you have EXPSPACE hardness.

For EXPSPACE completeness, observe that given two $\omega$ regular expressions $r_1$ and $r_2$, you can translate them to equivalent NBWs $A_1,A_2$, where the size of $A_i$ is at most single-exponential in the size of $r_1$. Then, checking whether $L(A_1)=L(A_2)$ can be done in PSPACE (nontrivial, but well known).

| cite | improve this answer | |

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.