Muller Automaton - Equivalence With Other ω-automata

Equivalence With Other ω-automata

The Muller automata are equally expressive as parity automata, Rabin Automata, Streett automata, and non-deterministic Büchi automata, to mention some, and strictly more expressive than the deterministic Büchi automata. The equivalence of the above automata and non-deterministic Muller automata can be shown very easily as the accepting conditions of these automata can be emulated using the acceptance condition of Muller automata. McNaughton's Theorem demonstrates the equivalence of non-deterministic Büchi automaton and deterministic Muller automaton. Thus, deterministic and non-deterministic Muller automaton are equivalent in terms of the languages they can accept.

Read more about this topic:  Muller Automaton