Rabin automaton
From Wikipedia, the free encyclopedia
A Rabin automaton is one of the many types of finite automata on infinite strings. It is of the form 
where 
and Σ are defined as for Büchi automata. 
is the transition function, and Ω is a set of pairs 
with 
. 
accepts the input word α if for the run 
of on α there exists an index i such that some state from Fi is visited infinitely often, while all states from Ei are visited finitely often.
[edit] See also
Streett automaton - A closely related automaton with the same components but a different acceptance condition.
[edit] References
- Automata on Infinite Objects, Handbook of Theoretical Computer Science (Vol. B), 1991. A survey by Wolfgang Thomas.
- Automata on Infinite Words Slides for a tutorial by Paritosh K. Pandya.
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
 |
This computer-related article is a stub. You can help Wikipedia by expanding it. |
