# Complexity of DBA-recognizable Omega-Languages

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.

• 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. – Denis Mar 12 '15 at 17:29