Rabin automaton
E836299
A Rabin automaton is a type of ω-automaton used in formal verification and automata theory to recognize sets of infinite sequences via Rabin acceptance conditions.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
automaton model
ⓘ
ω-automaton ⓘ |
| acceptanceConditionInformal | a run is accepting if there exists a pair (G,L) such that some state in G is visited infinitely often and no state in L is visited infinitely often ⓘ |
| canRecognizeAllLanguagesOf | nondeterministic Büchi automaton ⓘ |
| closureProperty |
closed under complementation
ⓘ
closed under intersection ⓘ closed under union ⓘ |
| definedOver | finite alphabet ⓘ |
| expressivePower | equivalent to other ω-regular formalisms ⓘ |
| expressivePowerEquivalentTo |
deterministic Muller automaton
ⓘ
deterministic parity automaton ⓘ nondeterministic Büchi automaton ⓘ |
| hasAcceptanceCondition | Rabin acceptance condition NERFINISHED ⓘ |
| hasComplexityAspect |
complementation can cause exponential blow-up in number of states
GENERATED
ⓘ
emptiness checking is decidable GENERATED ⓘ language inclusion is decidable GENERATED ⓘ |
| hasComponent |
acceptance pairs (G_i,L_i)
ⓘ
finite set of states ⓘ initial state ⓘ set of Rabin pairs ⓘ transition relation ⓘ |
| hasProperty | deterministic Rabin automata are as expressive as ω-regular languages ⓘ |
| hasVariant |
deterministic Rabin automaton
ⓘ
nondeterministic Rabin automaton ⓘ |
| introducedInContextOf | decision problems for infinite computations ⓘ |
| isDeterminizableVariantOf | Büchi automaton NERFINISHED ⓘ |
| mathematicalDomain |
logic in computer science
ⓘ
theoretical computer science ⓘ |
| namedAfter | Michael O. Rabin NERFINISHED ⓘ |
| operatesOn |
infinite sequences
ⓘ
infinite words ⓘ |
| recognizes | ω-regular languages ⓘ |
| relatedConstruction | Safra construction ⓘ |
| relatedTo |
Büchi automaton
NERFINISHED
ⓘ
Muller automaton NERFINISHED ⓘ Streett automaton NERFINISHED ⓘ parity automaton ⓘ |
| typicalUse |
automata-theoretic model checking of LTL formulas
ⓘ
deterministic representation of ω-regular specifications ⓘ |
| usedFor |
controller synthesis
ⓘ
specification of fairness properties ⓘ specification of liveness properties ⓘ synthesis of reactive systems ⓘ |
| usedIn |
automata theory
ⓘ
formal verification ⓘ model checking ⓘ reactive system verification ⓘ temporal logic verification ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Michael O. Rabin