Singleton Acceptance Conditions in

Abstract:  The regular !-languages can be defined by deterministic !-automata with the Rabin acceptance condition, referring to a list of pairs (Ek ; Fk) 1km of state sets of the automaton: A successful run should visit some Ek only finitely often but the corresponding Fk infinitely often. If only the non-existence, respectively existence of such visits is required, precisely the Staiger-Wagner definable !-languages are recognized. We study the question whether the sets Ek ; Fk can be reduced to singletons, i.e. whether one can refer to individual states in place of state sets. It is shown that for the usual Rabin acceptance condition this causes no loss of expressive power, while for the Staiger-Wagner case the acceptance by singletons leads to a proper restriction. 1 Introduction Acceptance conditions in !-automata serve to declare certain automaton runs to be "successful", usually by a restriction regarding the states which are infinitely often visited (or just: visited) in a run. All stand...