 Alternation (formal language theory)

In formal language theory, "alternation" refers to a concept primarily associated with alternating automata, a type of computational model that generalizes nondeterministic and deterministic automata. Alternating automata can be thought of as extending the idea of nondeterminism by allowing states to exist in a mode where they can make choices that are universally quantified (for all possible transitions) or existentially quantified (for some transition).