Alternating tree automata (Q1077932)

The concept of alternation has been introduced by Chandra, Stockmeyer and Kozen as a natural extension of the concept of nondeterminism. The effect of alternation has been studied in the context of computational complexity, automata theory, algebra, dynamic logic and combinatorial games. This paper discusses the effect of alternation on several varieties of tree automata. In the case of top-down tree automata, alternation turns out to be equivalent to nondeterminism. In the case of two-way tree automata, alternation turns out to be more powerful than nondeterminism and alternating two-way tree automata define exactly RECOG, the class of recognizable tree languages. When the two-way tree automata are also equipped with a synchronized pushdown facility, then the alternating version is equivalent to the deterministic one.