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.
The tree automaton A obtained from a schema specification D may have different characteristics according to the schema language used for D.
C1--Regular tree languages (RTL): A regular tree language is a language accepted by any tree automaton specified by Definition 1.
C2--Local tree languages (LTL): A local tree language is a regular tree language accepted by a tree automaton that does not have competing states.
C3--Single-type tree languages (STTL): A single-type tree language is a regular tree language accepted by a tree automaton having the following characteristics: (i) For each transition rule, the states in its regular expression do not compete with each other and (ii) the set [Q.
C4--Restrained-competition tree languages (RCTL): A restrained-competition tree language is a regular tree language accepted by a tree automaton having the following characteristics: (i) For each transition rule, its regular expression restraints competition of states and (ii) the set [Q.
The execution of a tree automaton A over an XML tree corresponds to the validation of the XML document wrt to the schema constraints represented by A.
For instance, in a run of a tree automaton for (simple) DTD, the sets [Q.
Let us suppose that there is a tree automaton A, representing the schema to be verified.
This test follows the definition of the run of the tree automaton.