Muller machine

The Muller automaton referred to Automata Theory , a 1963 by David E. Muller imagined concept of ω-automata . This type - deterministic as well as nondeterministic - has the same expressiveness as nondeterministic Büchi automata . In contrast, the number of states visited infinitely often is precisely defined, which allows more precise statements about acceptance behavior.

Muller machine for word recognition

A non-deterministic Muller automaton has the form . The following applies here: ${\displaystyle A=(Q,\Sigma ,q_{0},\Delta ,{\mathcal {F}})}$

• ${\displaystyle Q}$is the set of states, is the starting state ${\displaystyle q_{0}\in Q}$
• ${\displaystyle \Delta \subseteq Q\times \Sigma \times Q}$ is the transition relation
• ${\displaystyle {\mathcal {F}}\subseteq 2^{Q}}$is the board, d. H. for certain amounts ${\displaystyle {\mathcal {F}}=\lbrace F_{1},\dots ,F_{k}\rbrace }$ ${\displaystyle F_{1},\dots ,F_{k}\subseteq Q}$

For deterministic automata, the transition relation is a function , so it has clear images and the automaton therefore has clear runs. ${\displaystyle \delta \colon Q\times \Sigma \to Q}$

The Muller-acceptable ω-languages are the Boolean combinations of the deterministic-Büchi-recognizable ω-languages. Every deterministic Büchi automaton can be expressed as a Muller automaton. The class of Muller-recognizable ω-languages ​​is thus closed under Boolean operations. In order to construct a (nondeterministic) Büchi automaton for a Muller automaton, one lets the Büchi automaton guess which is the correct set, which has to be run through infinitely often, and from when the runs must begin. ${\displaystyle F_{i}\in {\mathcal {F}}}$

Acceptance behavior

A run is successful when , with . This is called the Muller Acceptance . ${\displaystyle \rho }$ ${\displaystyle \operatorname {Inf} (\rho )\in F}$ ${\displaystyle \operatorname {Inf} (\rho )=\lbrace q\in Q\mid q{\text{ erscheint unendlich oft in }}\rho \rbrace }$

${\displaystyle A}$ accepts a word when a run from on is successful. ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle \alpha }$

The Muller condition is: for one ${\displaystyle \operatorname {Inf} (\rho )=F_{i}}$ ${\displaystyle i=1,\dots ,k}$

In order to be accepted, a certain amount from the board has to be completely run through infinitely often. ${\displaystyle F_{i}}$ ${\displaystyle {\mathcal {F}}}$

Muller automat for tree recognition

A Muller tree automaton has the format where and are a set of subsets of . ${\displaystyle A=(Q,\Sigma ,q_{0},\Delta ,{\mathcal {F}})}$ ${\displaystyle \Delta \subseteq Q\times \Sigma \times Q\times Q}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle Q}$

A Muller tree automaton accepts a tree if there is a run from to such that on every path of the set of infinitely often occurring states is an element of . ${\displaystyle t}$ ${\displaystyle \rho }$ ${\displaystyle A}$ ${\displaystyle t}$ ${\displaystyle \rho }$ ${\displaystyle M}$ ${\displaystyle F}$

literature

• Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Ed.): Handbook of Theoretical Computer Science. Volume B: Formal Models and Semantics. Elsevier Science Publishers et al., Amsterdam et al. 1990, ISBN 0-444-88074-7 , pp. 133-164.