title: Alternating tree automata
text: # Alternating tree automata
  
  In automata theory, an alternating tree automaton (ATA) is an extension of nondeterministic tree automaton as same as alternating finite automaton extends nondeterministic finite automaton (NFA).
  
  ## Computational complexity
  
  The emptiness problem (deciding whether the language of an input ATA is empty) and the universality problem for ATAs are EXPTIME-complete. The membership problem (testing whether an input tree is accepted by an input AFA) is in PTIME.
  
  