Alternating tree automata

In automata theory, an alternating tree automaton (ATA) is a generalisation of a nondeterministic tree automaton in the same way that an alternating finite automaton is a generalisation of a nondeterministic finite automaton (NFA). == Computational complexity == The emptiness problem (deciding whether the language of an input ATA is empty) for ATAs, and therefore its complement, the universality problem, are EXPTIME-complete.

Source: Wikipedia — Alternating tree automata (CC BY-SA 4.0)