Streett automaton

Streett automaton

A Streett automaton is one of the many types of finite automata on infinite strings. It is of the form mathcal{A} = (Q,~Sigma,~q_0,~delta,~Omega) where Q,~q_0 and Sigma are defined as for Büchi automata. delta: Q imes Sigma ightarrow Q is the transition function, and Omega is a set of pairs (E_j,~F_j) with E_j, F_j subset Q. mathcal{A} accepts the input word alpha if for the run ho in Q^omega of mathcal{A} on alpha, for every index i, inf( ho)cap E_j eempty o inf( ho)cap F_j eempty (where inf( ho) is the group of states in Q that the run ho visits infinitely often).

Less formally, a Streett acceptance condition defines a set of ordered pairs (E,~F) of finite sets of states taken from the automaton's graph. A pair is satisfied by any run ~ ho that either does not contain infinitely many E states, or contains infinitely many E states and infinitely many F states. The Streett acceptance condition is met if all pairs are satisfied. The automaton may be nondeterministic, so an input word (which is infinite) may produce innumerable runs; the word is accepted if at least one run is accepted.

The acceptance condition is dual to the Rabin acceptance condition: The Streett condition is the logical negation of the Rabin condition, and therefore, if a language L can be recognized by a deterministic Streett automaton, then its complement ar{L} can be recognized by some deterministic Rabin automaton, and vice versa.

ee also

Rabin automaton - A closely related automaton with the same components but a different acceptance condition.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • ω-automaton — In automata theory, a branch of theoretical computer science, an ω automaton (or stream automaton) is a deterministic or nondeterministic automaton that runs on infinite, rather than finite, strings as input. Since ω automata do not stop, they… …   Wikipedia

  • Muller automaton — In automata theory, a Muller automaton is a type of an ω automaton. The acceptance condition separates a Muller automomaton from other ω automata. The Muller automata is defined using Muller acceptance condition, i.e. the set of all states… …   Wikipedia

  • Büchi automaton — A Büchi automaton is the extension of a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton (in case of a deterministic automaton, there is exactly one possible run) which… …   Wikipedia

  • Rabin automaton — Aside from the definition given below, a Rabin automaton may also refer to a type of probabilistic automaton. In mathematics, a Rabin automaton is one of the many types of finite automata on infinite strings. It is of the form mathcal{A} = (Q,… …   Wikipedia

  • Parity automaton — A parity automaton is a variant of a finite state automaton that accepts infinite inputs. Unlike usual finite state automata, there is no set of final states; instead, each state is assigned a natural number. It accepts an infinite input sequence …   Wikipedia

  • Shmuel Safra — Infobox Scientist name = Shmuel Safra image width = 150px caption = Shmuel Safra birth date = birth place = death date = death place = residence = citizenship = nationality = ethnicity = field = Computer Science, Complexity Theory work… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Automate sur les mots infinis — En informatique théorique, et spécialement en théorie des automates un automate sur les mots infinis ou ω automate est un automate fini, déterministe ou non, qui accepte des mots infins. Comme un tel automate ne s arrête pas, les conditions d… …   Wikipédia en Français

Share the article and excerpts

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