Transformations Induced by Tree Automata

Let tree automaton over Σ be arbitrary. We construct a deterministic tree automaton over Σ such that . We show that the following two statements are equivalent, (i) The ground tree transformation () induced by is equal to the ground tree transformation () induced by . (ii) There is a deterministic tree automaton over Σ such that the ground tree transformation () is equal to the ground tree transformation (). We compare relations and (). First we assume that is connected. We show that if and only if () = (). Hence Conditions (i) and (ii) are equivalent to Condition (iii). (iii) . Then we study an arbitrary tree automaton over Σ. We show that it is decidable if Condition (iii) holds