Alternating tree automata

In automata theory, an alternating tree automaton is an extension of nondeterministic tree automaton as same as alternating finite automaton extends nondeterministic finite automaton.

Computational complexity

The emptiness problem and the universality problem for ATAs are EXPTIME-complete. The membership problem is in PTIME.