Alternating tree automata
Extension of nondeterministic tree automaton
From Wikipedia, the free encyclopedia
In automata theory, an alternating tree automaton (ATA) is a generalisation of a nondeterministic tree automaton in the same way that a 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.[1] The membership problem (testing whether an input tree is accepted by an input AFA) is in PTIME[1].