Singleton Acceptance Conditions in omega-Automata

zum Volltext (213 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • August 1998
Seitenbereich18 Seiten

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.
Statische URL
IDNummer des Berichts :
  • Tr_9808