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 <math>\mathfrak{A} :=\left(Q,\Sigma,q_0,\delta,\mathcal{F}\right)</math> mit
- <math>Q</math> Zustandsmenge
- <math>\Sigma</math> Eingabealphabet
- <math>q_0 \in Q</math> Startzustand
- <math>\delta\colon Q \times \Sigma \to Q</math> Transitionsfunktion.
- <math>\mathcal{F}\subseteq2^Q</math> und <math>\mathcal{F}=\{F_1,..., F_k \}</math> für <math>F_i \subseteq Q</math>
Eigenschaften
<math>\mathfrak{A}</math> akzeptiert <math>\alpha \Longleftrightarrow Occ\left(\rho\right) \in \mathcal{F}</math> (z. B. <math>Occ\left(\rho\right)=F_1</math> oder ... oder <math>Occ\left(\rho\right)=F_k</math>) gilt für den Lauf <math>\rho</math> von <math>\mathfrak{A}</math> auf dem Wort <math>\alpha</math>.
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 <math>L:=\{\alpha \in \Sigma^\omega | \alpha\ beinhaltet\ aa\ aber\ kein\ b\}</math> eine ω-Sprache über <math>\Sigma=\{a,b,c\}</math>
Ein deterministischer Staiger-Wagner-Automat, der L erkennt ist dann z. B.:
<math>\mathfrak{A}_L=\left(Q,\Sigma,q_0,\delta,\mathcal{F}\right)</math> mit
<math>Q=\{1,2,3,4\}, q_0=0, \mathcal{F}=\{\{1,2,3\}\}</math> und
<math>\delta=\{</math>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<math>\}</math>
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 <math>F</math> akzeptierender Zustände und die Bedingung ist <math>Occ\left(\rho\right)\cap F\neq\emptyset</math>.
1'-Akzeptierung
Auch hier gibt es nur eine Menge akzeptierender Zustände und die Bedingung lautet <math>Occ\left(\rho\right)\subseteq F</math>.
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.
Literatur
- Ludwig Staiger und Klaus W. Wagner, Automatentheoretische und automatenfreie Characterisierungen topologischer Klassen regulärer Folgemengen, Elektronische Informationsverarbeitung und Kybernetik EIK, 10 (1974) 379–392.
- Erich Grädel, Wolfgang Thomas und Thomas Wilke (Herausgeber), Automata, Logics, and Infinite Games, LNCS 2500, 2002, Seite 20 (auf Englisch)
- Ludwig Staiger: ω-Languages. In: Grzegorz Rozenberg, Arto Salomaa (Hrsg.): Handbook of Formal Languages. Band 3: Beyond Words. Springer, Berlin u. a. 1997, ISBN 3-540-60649-1, S. 339–387.
- Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science. Band B: Formal Models and Semantics. Elsevier Science Publishers u. a., Amsterdam u. a. 1990, ISBN 0-444-88074-7, S. 133–192.
