Editing Tree automaton (section)

=== Recognizability ===

For a bottom-up automaton, a ground term ''t'' (that is, a tree) is accepted if there exists a reduction that starts from ''t'' and ends with ''q''(''t''), where ''q'' is a final state. For a top-down automaton, a ground term ''t'' is accepted if there exists a reduction that starts from ''q''(''t'') and ends with ''t'', where ''q'' is an initial state.

The tree language ''L''(''A'') '''accepted''', or '''recognized''', by a tree automaton ''A'' is the set of all ground terms accepted by ''A''. A set of ground terms is '''recognizable''' if there exists a tree automaton that accepts it.

A linear (that is, arity-preserving) tree homomorphism preserves recognizability.<ref>The notion in {{harvtxt|Comon et al.|2008|loc=sect. 1.4, theorem 1.4.3, p. 31-32}} of tree homomorphism is more general than that of the article "tree homomorphism".</ref>