Alternating finite automaton

In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into "existential" and "universal" transitions. For example, let "A" be an alternating automaton.
Note that due to the universal quantification a run is represented by a run "tree". "A" accepts a word "w", if there "exists" a run tree on "w" such that "every" path ends in an accepting state.
A basic theorem states that any AFA is equivalent to a deterministic finite automaton (DFA), hence AFAs accept exactly the regular languages.
An alternative model which is frequently used is the one where Boolean combinations are represented as "clauses". For instance, one could assume the combinations to be in disjunctive normal form so that formula_7 would represent formula_8. The state tt ("true") is represented by formula_9 in this case and ff ("false") by formula_10.
This clause representation is usually more efficient.
Alternating finite automata can be extended to accept trees in the same way as tree automata, yielding alternating tree automata.
Formal definition.
An alternating finite automaton (AFA) is a 6-tuple,
formula_11, where
The model was introduced by Chandra, Kozen and Stockmeyer.
State complexity.
Even though AFA can accept exactly the regular languages, they are different from other types of finite automata in the succinctness of description, measured by the number of their states.
Chandra et al. proved that converting an formula_23-state AFA to an equivalent DFA
requires formula_24 states in the worst case. Another construction by Fellah, Jürgensen and Yu. converts an AFA with formula_23 states to a nondeterministic finite automaton (NFA) with up to formula_26 states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.
Computational complexity.
The membership problem asks, given an AFA formula_27 and a word formula_28, whether formula_27 accepts formula_28. This problem is P-complete. This is true even on a singleton alphabet, i.e., when the automaton accepts a unary language.
The non-emptiness problem (is the language of an input AFA non-empty?), the universality problem (is the complement of the language of an input AFA empty?), and the equivalence problem (do two input AFAs recognize the same language) are PSPACE-complete for AFAs.