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 mit Zustandsmenge Eingabealphabet Startzustand Transitionsfunktion. und für
Eigenschaften akzeptiert (z. B. oder ... oder ) gilt für den Lauf von auf dem Wort .
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 mini|250px|Der zugehörige Automat Sei eine ω-Sprache über
Ein deterministischer Staiger-Wagner-Automat, der L erkennt ist dann z. B.: mit und 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 akzeptierender Zustände und die Bedingung ist .
1'-Akzeptierung Auch hier gibt es nur eine Menge akzeptierender Zustände und die Bedingung lautet .
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. Weblinks
Kategorie:Automatentheorie