Tree automaton

Tree automaton --- автомат над деревьями.

A tree automaton over an alphabet [math]\displaystyle{ \Sigma_{k} }[/math] is a quadruple [math]\displaystyle{ (S, S_{0}, S_{A}, f) }[/math], where [math]\displaystyle{ S }[/math] is a finite set of states; [math]\displaystyle{ S_{0} \in S }[/math] is the initial state; [math]\displaystyle{ S_{A} \subseteq S }[/math] is the set of accepting states; and [math]\displaystyle{ f: \; S \times S \times \Sigma_{k} \rightarrow S }[/math] is the transition function. Often the alphabet [math]\displaystyle{ \Sigma_{k} }[/math] is the set of graphs on [math]\displaystyle{ k+1 }[/math] or fewer (labeled) vertices.