From this grammar, it is easy to derive a tree automaton [20, 43]: the validation of the document wrt the schema is the run of this tree automaton over the XML tree.

A tree automaton can be built from a schema specified using schema languages such as DTD, XSD or RELAX NG.

Definition 1--Non-deterministic bottom-up finite tree automaton: A tree automaton over [SIGMA] is a tuple A = (Q, [SIGMA], [Q.sub.f], [DELTA] where Q is a set of states, [Q.sub.f] [subset or equal to] Q is a set of final states and [DELTA] is a set of transition rules of the form a, S, E [right arrow] q where (i) a [member of] [SIGMA]; (ii) S is a pair of disjoint sets of states, i.e., S = ([S.sub.compulsory], [S.sub.optional]) (with [S.sub.compulsory] [subset or equal to] Q and [S.sub.optional] [subset or equal to] Q); (iii) E is a regular expression over Q and (iv) q [member of] Q.

The tree automaton A obtained from a schema specification D may have different characteristics according to the schema language used for D.

Let A = (Q, [SIGMA], [Q.sub.f], [DELTA]) be a tree automaton. Two different states [q.sub.l] and [q.sub.2] in Q are competing if [DELTA] contains different transition rules (a, [S.sub.1], [E.sub.1] [right arrow] [q.sub.1] and a, [S.sub.2], [E.sub.2] [right arrow] [q.sub.2]) which share the same label a.

Clearly, tables encoding the tree automaton with static cost analysis tend to be larger than those where dynamic analysis is performed.

This difference in the matched sets would not be present when matching using a finite-state tree automaton which would report the matches V [right arrow] b and B [right arrow] b for both cases.

Thus, using the construction of a tree automaton as a step in a model-checking algorithm, seems a nonstartet, which can only yield algorithms that are far from optimal.

Consider a nondeterministic tree automaton A = <[Sigma], Q, [Delta], [q.sub.0], F>, where [Sigma] is the input alphabet, Q is a finite set of states, [Delta] is a transition function, [q.sub.0] [element of] Q is an initial state, and F specifies the acceptance condition (a condition that defines a subset of [Q.sub.[Omega]]; we define several types of acceptance conditions below).

We say that an alternating tree automaton is symmetric if it has the special structure described above.

Consider a run <T', r'> of A' (recall that one can regard a run of an alternating word automaton as a run of an alternating tree automaton with D = {1}).