In
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...
, an alternating tree automaton (ATA) is an extension of
nondeterministic tree automaton as same as
alternating finite automaton extends
nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state t ...
(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
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2''p''(''n'')) time, wh ...
.
[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
Automata (computation)
{{comp-sci-theory-stub