Singleton Acceptance Conditions in ω-Automata

Regular omega-languages can be defined by deterministic omega-automata with Rabin acceptance condition, referring to a list of pairs (E_k,F_k) (k = 1..m) of state sets of the automaton: A successful run should visit some E_k only finitely often but the corresponding F_k infinitely often. If only the non-existence, respectively existence of such visits is required, precisely the Staiger-Wagner definable omega-languages are recognized. We study the question whether the sets E_k, F_k 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.


Logo BII



Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.