Generalized automata on infinite trees and Muller-McNaughton's theorem (Q1178688)

The Muller-McNaughton's theorem characterizes those \(\omega\)-languages which are accepted by deterministic Muller automata in terms of \(\omega\)- languages accepted by deterministic Büchi automata and in terms of regular languages and their limits. The concepts of automata on infinite trees are introduced and various concepts of languages accepted by them are considered, too. The relations between them are investigated; in particular, a number of equivalences are proved. It is proved also that, in all considered cases, the nondeterministic top-down automata are more powerful than the deterministic ones some formally possibly generalizations of the Muller- McNaughton theorem are considered, and a number of them are proved to be wrong. The paper contains a very nice survey of previous work in this area and is written extremely clear.