Deterministic Büchi + its complement covers LTL?

Question

It is well known that deterministic Büchi automata (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). However, the argument often used is that DBA are not closed under complementation - that is there is a language $\mathcal D$ recognized by DBA, but $\mathcal D^c$ is not recognized by any DBA. As an example, $\mathcal D = (b^*a)^\omega$ and $\mathcal D^c = (a+b)^*a^\omega$.

I wonder though, whether for any $\omega$-regular language $\mathcal L$ it holds either $\mathcal L$ is recognized by some DBA, or $\mathcal L^c$ is recognized by some DBA. If not, what is an example of a language which is not recognizable by DBA and which complement is not recognizable either?

Answer 1

From your example, it is easy to derive a language $L$, such that neither $L$ nor its complement is recognized by a DBA.

Take an alphabet of four letter $\{a,b,c,d\}$, and let $L=((a+b)^* a^\omega)+(c^*d)^\omega$. It is not DBA-recognizable because of the $\{a,b\}$-part, and its complement is not because of the $\{c,d\}$-part.

For a less artificial example, you can for instance take on alphabet $\{a,b,c\}$ the language $L$ of words with infinitely many $b$ and finitely many $c$. Both $L$ and its complement have to check that the number of something is finite, so both are not DBA-recognizable.