Parity automaton

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 if and only if there exists a run of the automaton (in case of a deterministic automaton, there is exactly one possible run) that satisfies the parity condition: the largest number occurring infinitely often is even.

Parity automata are generalizations of Büchi automata. Streett, Rabin, and Muller automata are generalizations of parity automata.


Soft Eng logo This computer language-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../p/a/r/Parity_automaton.html"