1-Akzeptanz

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.

Inhaltsverzeichnis

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

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 ρ 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.

Beispiel

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.

1-Akzeptanz

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

1'-Akzepztanz

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.

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)

Wikimedia Foundation.

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

  • 1'-Akzeptanz — 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.… …   Deutsch Wikipedia

  • Akzeptanz — (von lat. „accipere“ für gutheißen, annehmen, billigen) ist eine Substantivierung des Verbes akzeptieren, welches verstanden wird als annehmen, anerkennen, einwilligen, hinnehmen, billigen, mit jemandem oder etwas einverstanden sein.… …   Deutsch Wikipedia

  • Akzeptanz — Akzeptanz,die:⇨Billigung(1) …   Das Wörterbuch der Synonyme

  • Akzeptanz- und Commitmenttherapie — Die Akzeptanz und Commitmenttherapie (ACT, gesprochen wie das englische Wort act) ist eine neuere Form der Psychotherapie, bei der klassische verhaltenstherapeutische Techniken mit achtsamkeits und akzeptanzbasierten Strategien und mit… …   Deutsch Wikipedia

  • 1-EURO-Jobs — Die Arbeitsgelegenheit mit Mehraufwandsentschädigung (AGH MAE) ist nach § 16d eine zusätzliche und im öffentlichen Interesse stehende Tätigkeit (Arbeitsgelegenheit) für Empfänger von Arbeitslosengeld II. Bis zum 31. Dezember 2008 war sie… …   Deutsch Wikipedia

  • 1-Euro-Job — Die Arbeitsgelegenheit mit Mehraufwandsentschädigung (AGH MAE) ist nach § 16d eine zusätzliche und im öffentlichen Interesse stehende Tätigkeit (Arbeitsgelegenheit) für Empfänger von Arbeitslosengeld II. Bis zum 31. Dezember 2008 war sie… …   Deutsch Wikipedia

  • 1-€-Job — Die Arbeitsgelegenheit mit Mehraufwandsentschädigung (AGH MAE) ist nach § 16d eine zusätzliche und im öffentlichen Interesse stehende Tätigkeit (Arbeitsgelegenheit) für Empfänger von Arbeitslosengeld II. Bis zum 31. Dezember 2008 war sie… …   Deutsch Wikipedia

  • 1 Euro Job — Die Arbeitsgelegenheit mit Mehraufwandsentschädigung (AGH MAE) ist nach § 16d eine zusätzliche und im öffentlichen Interesse stehende Tätigkeit (Arbeitsgelegenheit) für Empfänger von Arbeitslosengeld II. Bis zum 31. Dezember 2008 war sie… …   Deutsch Wikipedia

  • 1. Oktober — Der 1. Oktober ist der 274. Tag des Gregorianischen Kalenders (der 275. in Schaltjahren), somit bleiben 91 Tage bis zum Jahresende. Historische Jahrestage September · Oktober · November 1 2 …   Deutsch Wikipedia

  • Akzeptanz — Ak|zep|tanz die; , en <zu ↑...anz>: 1. (bes. Werbespr.) Bereitschaft, etwas (ein neues Produkt o. Ä.) anzunehmen. 2. bejahende od. tolerierende Einstellung von Personen od. Gruppen gegenüber Neuerungen u. Entwicklungen in Wirtschaft,… …   Das große Fremdwörterbuch

Share the article and excerpts

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