k-COUNTING AUTOMATA
In this paper, we define k-counting automata as recognizers for omega-languages, i.e. languages of infinite words. We prove that the class of omega-languages they recognize is a proper extension of the omega-regular languages. In addition we prove that languages recognized by k-counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for k-counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe so.
omega-automata extensions to regular omega-languages closure under boolean operations emptiness problem infinite hierarchy of omega-languages