A tree automaton is a type of finite state machine. Tree automata deal with tree structures, rather than the strings of more conventional finite state machines.

According to how the automata runs on the input tree, it can be of two types (a) Top Down (b) Bottom Up.

Top Down

Can be described as a (Q, \Gamma, q_0, \delta, F). Here Q is the finite set of states, q_0 is the initial state \in Q, F is the set of final states and \delta is the transition function.

The automata starts on the root of the tree with the initial state. Reads the symbol and branches into as many states as the number of children. The tree is assumed to be accepted if it is accepted at all the leaves.

Bottom Up

Can be described as a (Q, \Gamma, q_0, \delta, F). Here Q is the finite set of states, q_0 is the initial state \in Q, F is the set of final states and \delta is the transition function.

The automata starts with the initial state simultaneously at all the leaves. According to states of the child and the input symbols the root is labelled with the next state. The tree is accepted if the state labeled at the root is accepting state.

External links

See http://www.grappa.univ-lille3.fr/tata