tree automaton


Also found in: Wikipedia.

tree automaton

[′trē ‚ȯd·ə‚mā·shən]
(computer science)
An automaton that processes inputs in the form of trees, usually trees associated with parsing expressions in context-free languages.
References in periodicals archive ?
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.
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.
We then say that A is a fixed arity tree automaton.
We say that an alternating tree automaton is symmetric if it has the special structure described above.
We define an alternating tree automaton A that accepts exactly all {a, b, c}-labeled binary trees in which all paths have a node labeled a and there exists a path with two successive b labels.