Access Restriction

Author Leoniuk, Barbara ♦ Lescow, Helmut ♦ Thomas, Wolfgang
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Singleton Acceptance Condition ♦ State Set ♦ Singleton Lead ♦ Proper Restriction ♦ Individual State ♦ Rabin Acceptance Condition ♦ Usual Rabin Acceptance Condition ♦ Staiger-wagner Case ♦ Staiger-wagner Definable Language ♦ Regular Language ♦ Deterministic Automaton ♦ Expressive Power ♦ Successful Run
Abstract Regular ω-languages can be defined by deterministic ω-automata with Rabin acceptance condition, referring to a list of pairs (E k ; F k ) 1km 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 !-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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 1998-01-01