1'-Akzeptanz

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:

  • 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 — Aufnahme; Akzeptierung; Annahme; Bejahung; Wohlwollen; Zustimmung * * * Ak|zep|tạnz 〈f. 20; unz.〉 das Akzeptieren, das Bereitsein, etwas anzunehmen ● hohe, niedrige Akzeptanz; in der Bevölkerung besteht keine Akzeptanz für den weiteren Ausbau… …   Universal-Lexikon

  • 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

  • Akzeptanz — die Akzeptanz (Mittelstufe) Bereitschaft, etw. anzunehmen Beispiele: Sein Vorschlag hat große Akzeptanz gefunden. Diese Idee hat allgemeine Akzeptanz unter den Schülern …   Extremes Deutsch

  • Akzeptanz — Ak|zep|tạnz 〈f.; Gen.: ; Pl.: unz.〉 das Akzeptieren, das Bereitsein, etwas anzunehmen; in der Bevölkerung besteht keine Akzeptanz für den weiteren Ausbau der Atomenergie [Etym.: → Akzeptant] …   Lexikalische Deutsches Wörterbuch

  • Akzeptanz — Bereitschaft, einen Sachverhalt billigend hinzunehmen. A. gegenüber einem Gegenstand wird als Teilaspekt der ⇡ Konformität im Spektrum zwischen Gehorsam, Anpassung, Akzeptanz, Verinnerlichung gesehen. Neben der zeitpunktbezogenen A. interessiert… …   Lexikon der Economics

  • Akzeptanz — akzeptieren »annehmen; billigen«: Das Verb wurde im 15. Jh. aus gleichbed. lat. ac ceptare entlehnt, einer Intensivbildung zu gleichbed. lat. ac cipere (vgl. ↑ kapieren). – Dazu das Adjektiv akzeptabel »annehmbar« (Mitte 17. Jh.; über… …   Das Herkunftswörterbuch

  • Akzeptanz — Ak·zep·tạnz die; nur Sg; die Bereitschaft, etwas Neues zu akzeptieren …   Langenscheidt Großwörterbuch Deutsch als Fremdsprache

  • 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

  • Akzeptanz — Ak|zep|tạnz, die; , en (Bereitschaft, etwas zu akzeptieren) …   Die deutsche Rechtschreibung

Share the article and excerpts

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