We consider co-Buechi tree automata along with both alternating and generalized paradigms, as a characterization of the class of languages whose complement is accepted by generalized Buechi tree automata. We first prove that for alternating generalized co-Buechi tree automata the simulation theorem does not hold and the generalized acceptance does not add to the expressive power of the model. Then, we show that the emptiness problem for this class is EXPTIME-complete. For the class of languages whose complement is accepted by deterministic generalized Buechi tree automata, we get better complexity bounds: we give a characterization of this class in terms of generalized co-Buechi tree automata that yields an algorithm for checking the emptiness that takes time linear in the product of the number of states and the number of sets in the acceptance condition. Finally, we compare the classes of languages whose complement is respectively accepted by deterministic and nondeterministic Buechi tree automata with the main classes studied in the literature.
展开▼
