k-COUNTING AUTOMATA

摘要

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 fc-counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe so.