Editing Tree automaton (section)

{{for|a different notion of tree automaton|tree walking automaton}}

A '''tree automaton''' is a type of [[state machine]]. Tree automata deal with [[tree structure]]s, rather than the [[string (computer science)|strings]] of more conventional state machines.

The following article deals with branching tree automata, which correspond to [[regular tree language|regular languages of trees]].

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.)