Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular expression to a Muller automaton. However, I would asumme that this problem lies in NP but I could not find any proofs of this.

  • 6
    $\begingroup$ Your problem is not likely to be in NP: universality of standard regular expressions is already PSPACE-complete. Therefore we can show that your problem is PSPACE-hard: if $e$ is a regular expression on $\{a,b\}$ the language $(a+b+\sharp)^*(e\sharp)^\omega$ is DBA-recognizable on $\{a,b,\sharp\}$ iff $e$ is universal. $\endgroup$ – Denis Mar 12 '15 at 17:29

Your Answer

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

Browse other questions tagged or ask your own question.