 a tree automaton is a type of state machine. tree automata deal with tree structures, rather than the strings of more conventional state machines. the following article deals with branching tree automata, which correspond to regular languages of trees. for a different notion of tree automaton, see tree walking automaton. as with classical automata, finite tree automata (fta) can be either a deterministic automaton or not. according to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. this is an important issue, as although non-deterministic (nd) top-down and nd bottom-up tree automata are equivalent in expressive power, deterministic top-down automata are strictly less powerful than their deterministic bottom-up counterparts, because tree properties specified by deterministic top-down tree automata can only depend on path properties. (deterministic bottom-up tree automata are as powerful as nd tree automata.) ==definitions== a ranked alphabet is a pair of an ordinary alphabet f and a function arity: fââ. each letter in f has its arity so it can be used to build terms. nullary elements (of zero arity) are also called constants. terms built with unary symbols and constants can be considered as strings. higher arities leads to proper trees. a bottom-up finite tree automaton over f is defined as a tuple (q, f, q'f, Î), where q is a set of unary letters used as states, f is a ranked alphabet, q'f â q is a set of final states, and Î is a set of transition rules of the form f(q1(x1),...,q'n(x'n)) â q(f(x1,...,x'n)), for an n-ary f â f, q, q'i â q, and x'i variables denoting subtrees. that is, members of Î are rewrite rules from nodes whose childs' roots are states, to nodes whose roots are states. thus the state of a node is deduced from the states of its children. for n=0, that is, for a constant symbol f, the above transition rule definition reads f() â q(f()); often the empty parentheses are omitted for convenience: f â q(f). since these transition rules for constant symbols (leaves) do not require a state, no explicitly definied initial states are needed. a tree automaton is run on a ground term over f, starting at the leaves and moving upwards, associating a run state from q with each subterm. the tree is accepted if its root is associated to an accepting state from q'f.{{#tag:ref|comon et al.{{cite book| author=h. comon, m. dauchet, r. gilleron, f. jacquemard and d. lugiez, s. tison, m. tommasi| title=tree autom
Automata_theory Trees_(data_structures)