Alternating tree automataIn automata theory, an alternating tree automaton is an extension of nondeterministic [tree automaton] as same as alternating [finite automaton] extends nondeterministic finite automaton.Computational complexityThe emptiness problem and the universality problem for ATAs are EXPTIME-complete. The membership problem is in PTIME.