Accepted: 13 June 2012
In this paper, we define k-counting automata as recognizers for ω-languages, i.e. languages of infinite words. We prove that the class of ω-languages they recognize is a proper extension of the ω-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.
Mathematics Subject Classification: 68Q45 / 20F10
Key words: ω-automata / extensions to regularω-languages / closure under Boolean operations / emptiness problem / infinite hierarchy ofω-languages
© EDP Sciences 2012