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
  • Σ Eingabealphabet
  • q_0 \in Q Startzustand
  • \delta\colon Q \times \Sigma \to Q Transitionsfunktion.
  • \mathcal{F}\subseteq2^Q und \mathcal{F}=\{F_1,..., F_k \} für F_i \subseteq Q


\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 ρ von \mathfrak{A} auf dem Wort α.

Eine ω-Sprache ist Staiger-Wagner-erkennbar, gdw. sie eine boolesche Kombination von E-erkennbaren ω-Sprachen ist. Sie ist außerdem Staiger-Wagner-erkennbar, gdw. sie deterministisch Büchi-erkennbar und deterministisch co-Büchi-erkennbar ist.


der zugehörige Automat

Sei L:=\{\alpha \in \Sigma^\omega | \alpha\ beinhaltet\ aa\ aber\ kein\ b\} eine ω-Sprache über Σ = {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
δ = {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 Akzeptanzbedingungen

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


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


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.


  • 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)

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 1 — adj. 1. used of a single unit or thing; not two or more; representing the number one as an Arabic numeral Syn: one, i, ane [WordNet 1.5 +PJC] …   The Collaborative International Dictionary of English

  • 1 — Year 1 (I) was a common year starting on Saturday of the Julian calendar. The preceding year is 1 BC in the widely used Gregorian calendar or in its predecessor, the Julian calendar, neither of which has a Year zero . NOTOC EventsBy placeRoman… …   Wikipedia

  • +1 — See also: Plus One +1 can mean:* +1, the ITU country code for the North American Numbering Plan Area, including the United States, Canada, and parts of the Caribbean * +1, a rare or high quality version of an item in a role playing game * Chase… …   Wikipedia

  • $1 — There are many $1 banknotes, bills or coins, including: Australian one dollar coin which replaced the one dollar note Loonie which replaced the one dollar bill United States one dollar bill Dollar coin (United States) New Zealand one dollar coin …   Wikipedia

  • 1,2-Dibromoethane — IUPAC name …   Wikipedia

  • −1 (number) — −1 −1 0 1 2 3 4 5 6 7 8 9 → List of numbers Integers 0 10 20 30 …   Wikipedia

  • 1 Utama — Shopping Mall Location Bandar Utama, Petaling Jaya, Selangor, Malaysia Opening date 1995 Developer …   Wikipedia

  • 1-Pentanol — 1 Pentanol …   Wikipedia

  • 1-Hexanol — IUPAC name …   Wikipedia

  • 1 Squadron SAAF — 1 Squadron Two retired Mirage F1 s (CZ s and not AZ s as flown by 1 Sqn)at Ysterplaat AFB Museum Active February 1920 to 25 November 1997 …   Wikipedia

  • 1 Esdras — (Εσδράς A′) is a book from the Septuagint translation of the Old Testament regarded as canonical in Eastern and Oriental Orthodoxy, but regarded as apocryphal by Jews, Catholics, and most Protestants. It is listed among the Apocrypha in Article… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”