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 — 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,2-Dibromoethane — IUPAC name …   Wikipedia

  • 1-up — (or “1UP”, “1 UP”, etc.), pronounced one up , is a term in console video gaming that commonly refers to an item that gives the player an extra life,[1][2] to complete the game. In certain games, it is possible to receive multiple extra lives at… …   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

  • 1,8-Bis(dimethylamino)naphthalene — 1,8 Bis(dimethylamino)naphthalene …   Wikipedia

Share the article and excerpts

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