Parity automaton

From Wikipedia, the free encyclopedia

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. It is equivalent to require that the least number occurring infinitely often be even.

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