down a given path, information from other paths is inaccessible. Consider the transducer coding the transformation ; that is, output the right child of the input. This is easily done by a rule , where p encodes the identity. Now let's say we want to restrict this transducer to the finite (and thus, in particular, regular) domain . We must use the rules . But in the first rule, does not appear at all, since nothing is produced from the left child. Thus, it is not possible to test that the left child is c. In contrast, since we produce from the right child, we can test that it is a or b. In general, the criterion is that DTOP cannot test properties of subtrees from which they do not produce output. DTOP are not closed under composition. However this problem can be solved by the addition of a lookahead: a tree automaton, coupled to the transducer, that can perform tests on the domain which the transducer is incapable of. This follows from the point about domain restriction: composing the DTOP encoding identity on with the one encoding must yield a transducer with the semantics , which we know is not expressible by a DTOP. The typechecking problem—testing whether the image of a regular tree language is included in another regular tree language—is decidable. The equivalence problem—testing whether two DTOP define the same functions—is decidable. Bottom-Up Tree Transducers (BOT) As in the simpler case of tree automata, bottom-up tree transducers are defined similarly to their top-down counterparts, but proceed from the leaves of the tree to the root, instead of from the root to the leaves. Thus the main difference is in the form of the rules, which are of the form . References Trees (data structures) Automata (computation) Finite automata Formal languages Theoretical computer science