Muller Automaton

Get Muller Automaton essential facts below. View Videos or join the Muller Automaton discussion. Add Muller Automaton to your PopFlock.com topic list for future reference or share this resource on social media.
## Formal definition

## Equivalence with other ?-automata

## Transformation to non-deterministic Muller automaton

## Transformation to deterministic muller automaton

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Muller Automaton

In automata theory, a **Muller automaton** is a type of an ?-automaton.
The acceptance condition separates a Muller automaton from other ?-automata.
The Muller automaton is defined using Muller acceptance condition, i.e. the set of all states visited infinitely often must be an element of the acceptance set. Both deterministic and non-deterministic Muller automata recognize the ?-regular languages. They are named after David E. Muller, an American mathematician and computer scientist, who invented them in 1963.^{[1]}

Formally, a **deterministic Muller-automaton** is a tuple *A* = (*Q*,?,?,*q*_{0},**F**) that consists of the following information:

*Q*is a finite set. The elements of*Q*are called the*states*of*A*.- ? is a finite set called the
*alphabet*of*A*. - ?:
*Q*× ? ->*Q*is a function, called the*transition function*of*A*. *q*_{0}is an element of*Q*, called the initial state.**F**is a set of sets of states. Formally,**F**?**P**(*Q*) where**P**(*Q*) is powerset of*Q*.**F**defines the*acceptance condition*.*A*accepts exactly those runs in which the set of infinitely often occurring states is an element of**F**

In a **non-deterministic Muller automaton**, the transition function ? is replaced with a transition relation ? that returns a set of states and initial state is *q*_{0} is replaced by a set of initial states *Q*_{0}. Generally, Muller automaton refers to non-deterministic Muller automaton.

For more comprehensive formalism look at ?-automaton.

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.

Following is a list of automata constructions which transforms a type of ?-automata to a non-deterministic Muller automaton.

- From Büchi automaton
- If is the set of final states in a Büchi automata with the set of states , we can construct a Muller automata with same set of states, transition function and initial state with the muller accepting condition as
**F**= { X | X ? 2^{Q}? X ? B ? }

- From Rabin automaton/Parity automaton
- Similarly, the Rabin conditions can be emulated by constructing the acceptance set in the Muller automata as all sets in which satisfy , for some j. Note that this covers the case of Parity automaton too, as the Parity acceptance condition can be expressed as Rabin acceptance condition easily.

- From Streett automaton
- The Streett conditions can be emulated by constructing the acceptance set in the Muller automata as all sets in which satisfy , for all j.

- Union of two deterministic muller automaton

- From Büchi automaton

McNaughton's Theorem provides a procedure to transform non-deterministic Büchi automaton to deterministic Muller automaton.

**^**Muller, David E. (1963). "Infinite sequences and finite machines".*4th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT)*: 3-16.

- Automata on Infinite Words Slides for a tutorial by Paritosh K. Pandya.
- Yde Venema (2008) Lectures on the Modal ?-calculus; the 2006 version was presented at The 18th European Summer School in Logic, Language and Information

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists