Infinity problems and countability problems for omega-automata
The infinity problem for w-automata is to decide if the w-language recognized by a given automaton is infinite; the countability problem is to decide if a given automaton recognizes a countable w-language. We prove that these problems are NLogspace-complete for (nondeterministic) Buchi, generalized Buchi, Muller, Rabin and parity automata. (c) 2006 Elsevier B.V. All rights reserved.
formal languages omega-automaton cardinality complexity