Following introductory chapters describing schemas, tree automata
, patterns, and marking automata, the first section concludes with a chapter on the XML processing language and its typechecking algorithm.
In this paper, we show that alternating tree automata are the key to a comprehensive automata-theoretic framework for branching temporal logics.
 avoids the construction of tree automata that correspond to [Mu]-calculus formulas.)
In this paper, we argue that alternating tree automata are the key to a comprehensive and satisfactory automata-theoretic framework for branching temporal logics.
ALTERNATING TREE AUTOMATA. A tree is a set T [subset or equal to] N* such that if x [multiplied by] c [element of] T where x [element of] N* and c [element of] N, then also x [element of] T, and for all 0 [is less than or equal to] c' [is less than] c, x [multiplied by] c' [element of] T.
Automata over infinite trees (tree automata) run over [Sigma]-labeled trees that have no leaves [Thomas 1990].
It is shown there how to use alternating tree automata to obtain space-efficient model checking methods.
Finite automata on infinite trees (tree automata, for short) run on such [Sigma]-labeled trees.
In nondeterministic tree automata, each disjunct in [Delta] is a conjunction with exactly one element associated with each direction.
A HAA over binary trees is a tuple A = <[Sigma], Q, [Delta], [Q.sub.0], [Alpha]>, where [Sigma], Q, [Delta], and [Q.sub.0] are as in usual alternating tree automata and [Alpha] = <G, B>, with G [subset or equal to] Q and B [subset or equal to] Q, is the acceptance condition.
Given a set D [subset] IN of branching degrees, a HAA over D-trees is then A = <[Sigma], D, Q, [Delta], q0, [Alpha]), where, as with alternating tree automata, [Delta] : Q x [Sigma] x D [right arrow] [B.sup.+](IN x Q) takes the branching degree of the current node in the input as an additional argument.