Staiger-Wagner machine

The Staiger-Wagner automaton (named after Ludwig Staiger and Klaus Wagner ) is an ω-automaton and is an analogue to the Muller automaton . The languages recognized by Staiger-Wagner automata are a subset of the ω-regular languages.

Formal definition

A Staiger-Wagner automaton is a 5-tuple with ${\displaystyle {\mathfrak {A}}:=\left(Q,\Sigma ,q_{0},\delta ,{\mathcal {F}}\right)}$

• ${\displaystyle Q}$ State quantity
• ${\displaystyle \Sigma }$ Input alphabet
• ${\displaystyle q_{0}\in Q}$ Starting state
• ${\displaystyle \delta \colon Q\times \Sigma \to Q}$ Transition function.
• ${\displaystyle {\mathcal {F}}\subseteq 2^{Q}}$and for ${\displaystyle {\mathcal {F}}=\{F_{1},...,F_{k}\}}$ ${\displaystyle F_{i}\subseteq Q}$

properties

${\displaystyle {\mathfrak {A}}}$accepted (e.g. or ... or ) applies to the run of on the word . ${\displaystyle \alpha \Longleftrightarrow Occ\left(\rho \right)\in {\mathcal {F}}}$ ${\displaystyle Occ\left(\rho \right)=F_{1}}$ ${\displaystyle Occ\left(\rho \right)=F_{k}}$ ${\displaystyle \rho }$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle \alpha }$

An ω-language is Staiger-Wagner-recognizable if and only if it is a Boolean combination of 1-recognizable (see below) ω-languages. It can also be recognized by Staiger-Wagner, if necessary. it is both deterministically Büchi- knowable and deterministically co-Büchi- knowable .

example

the associated automat

Let be an ω-language over ${\displaystyle L:=\{\alpha \in \Sigma ^{\omega }|\alpha \ beinhaltet\ aa\ aber\ kein\ b\}}$ ${\displaystyle \Sigma =\{a,b,c\}}$

A deterministic Staiger-Wagner automaton that recognizes L is then e.g. E.g .: with and 1 / a → 2, 1 / b → 4, 1 / c → 1,       2 / a → 3, 2 / b → 4, 2 / c → 1,       3 / a → 3, 3 / b → 4, 3 / c → 3,       4 / a → 4, 4 / b → 4, 4 / c → 4
${\displaystyle {\mathfrak {A}}_{L}=\left(Q,\Sigma ,q_{0},\delta ,{\mathcal {F}}\right)}$ ${\displaystyle Q=\{1,2,3,4\},q_{0}=0,{\mathcal {F}}=\{\{1,2,3\}\}}$
${\displaystyle \delta =\{}$


${\displaystyle \}}$

Exactly when the automaton visits states 1, 2 and 3 but not 4, α is accepted.

Related Terms of Acceptance

The following two acceptance conditions are closely related to the Staiger-Wagner condition.

1 acceptance

There are just a lot of accepting states here and the condition is . ${\displaystyle F}$ ${\displaystyle Occ\left(\rho \right)\cap F\neq \emptyset }$

1 'acceptance

Again, there are just a lot of accepting states and the condition is . ${\displaystyle Occ\left(\rho \right)\subseteq F}$

Transformation into a Büchi machine

In order to transform a Staiger-Wagner automaton into a Büchi automaton that recognizes the same language, an exponential number of states are generally required. This explosion of the quantity of states does not apply to 1-acceptance and 1'-acceptance.

literature

• Ludwig Staiger and Klaus W. Wagner , automaton-theoretical and automaton-free characterizations of topological classes of regular sequences, electronic information processing and cybernetics EIK, 10 (1974) 379–392.
• Erich Grädel, Wolfgang Thomas and Thomas Wilke (editors), Automata, Logics, and Infinite Games, LNCS 2500, 2002, page 20 (in English)
• Ludwig Staiger: ω-Languages . In: Grzegorz Rozenberg , Arto Salomaa (Ed.): Handbook of Formal Languages. Volume 3: Beyond Words. Springer, Berlin et al. 1997, ISBN 3-540-60649-1 , pp. 339-387.
• 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-192.

Web links

Commons : Staiger-Wagner-Automat  - collection of pictures, videos and audio files