tree automaton

(redirected from Tree automata)

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 ?
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.
Schema constraints are represented by tree automata and tree grammars.
In this paper, we show that alternating tree automata are the key to a comprehensive automata-theoretic framework for branching temporal logics.
[1993] 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.