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.
allows, in the spirit of Wolper [1983], nondeterministic tree automata as operators.
Alternating automata generalize nondeterministic tree automata and were first introduced in Muller and Schupp [1987] (see Slutzki [1985] for alternating automata on finite trees).
It is shown there how to use alternating tree automata to obtain space-efficient model checking methods.
Alternating automata on infinite trees generalize nondeterministic tree automata and were first introduced in Muller and Schupp [1987].
In nondeterministic tree automata, each disjunct in [Delta] is a conjunction with exactly one element associated with each direction.
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.