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.

Vorschau

Logo BII

BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.