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 — 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,1,1,2-Tetrafluoroethane — 1,1,1,2 Tetrafluoroethane …   Wikipedia

  • 1, 2 Step — Single by Ciara featuring Missy Elliott from the album Goodies …   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

Share the article and excerpts

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