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.H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, Tree Automata Techniques and Applications (Theorem 7.5.1 and subsequent remark) The membership problem (testing whether an input tree is accepted by an input AFA) is in PTIME.

References