Staiger-Wagner-Automat
# Staiger-Wagner-Automat

Der Staiger-Wagner-Automat (benannt nach Ludwig Staiger und Klaus Wagner) ist ein ω-Automat und bildet ein Analogon zum Muller-Automaten. Die von Staiger-Wagner-Automaten erkannten Sprachen sind eine Untermenge der ω-regulären Sprachen.

## Formale Definition

Ein Staiger-Wagner-Automat ist ein 5-Tupel ${\mathfrak {A}}:=\left(Q,\Sigma ,q_{0},\delta ,{\mathcal {F}}\right)$ mit

* $Q$ Zustandsmenge
* $\Sigma$ Eingabealphabet
* $q_{0}\in Q$ Startzustand
* $\delta \colon Q\times \Sigma \to Q$ Transitionsfunktion.
* ${\mathcal {F}}\subseteq 2^{Q}$ und ${\mathcal {F}}=\{F_{1},...,F_{k}\}$ für $F_{i}\subseteq Q$

## Eigenschaften

${\mathfrak {A}}$ akzeptiert $\alpha \Longleftrightarrow Occ\left(\rho \right)\in {\mathcal {F}}$ (z. B. $Occ\left(\rho \right)=F_{1}$ oder ... oder $Occ\left(\rho \right)=F_{k}$) gilt für den Lauf $\rho$ von ${\mathfrak {A}}$ auf dem Wort $\alpha$.

Eine ω-Sprache ist genau dann Staiger-Wagner-erkennbar, wenn sie eine boolesche Kombination von 1-erkennbaren (s. unten) ω-Sprachen ist. Sie ist außerdem Staiger-Wagner-erkennbar, gdw. sie sowohl deterministisch Büchi-erkennbar als auch deterministisch co-Büchi-erkennbar ist.

## Beispiel

Sei $L:=\{\alpha \in \Sigma ^{\omega }|\alpha \ beinhaltet\ aa\ aber\ kein\ b\}$ eine ω-Sprache über $\Sigma =\{a,b,c\}$

Ein deterministischer Staiger-Wagner-Automat, der L erkennt ist dann z. B.: ${\mathfrak {A}}_{L}=\left(Q,\Sigma ,q_{0},\delta ,{\mathcal {F}}\right)$ mit $Q=\{1,2,3,4\},q_{0}=0,{\mathcal {F}}=\{\{1,2,3\}\}$ und $\delta =\{$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$\$

Genau dann wenn der Automat die Zustände 1, 2 und 3 aber nicht 4 besucht, wird α akzeptiert.

## Verwandte Akzeptierungsbedingungen

Mit der Staiger-Wagner-Bedingung sind die beiden folgenden Akzeptierungsbedingungen nahe verwandt.

### 1-Akzeptierung

Hier gibt es nur eine Menge $F$ akzeptierender Zustände und die Bedingung ist $Occ\left(\rho \right)\cap F\neq \emptyset$.

### 1'-Akzeptierung

Auch hier gibt es nur eine Menge akzeptierender Zustände und die Bedingung lautet $Occ\left(\rho \right)\subseteq F$.

## Transformation in einen Büchi-Automaten

Um einen Staiger-Wagner-Automaten in einen Büchi-Automaten, der dieselbe Sprache erkennt, zu transformieren, werden im Allgemeinen exponentiell viele Zustände gebraucht. Diese Explosion der Zustandsmenge entfällt bei 1-Akzeptanz und 1'-Akzeptanz.

