Tree transducer

In theoretical computer science and formal language theory, a tree transducer (TT) is an abstract machine taking as input a tree, and generating output – generally other trees, but models producing words or other structures exist. Roughly speaking, tree transducers extend tree automata in the same way that word transducers extend word automata.
Manipulating tree structures instead of words enable TT to model syntax-directed transformations of formal or natural languages. However, TT are not as well-behaved as their word counterparts in terms of algorithmic complexity, closure properties, etcetera. In particular, most of the main classes are not closed under composition.
The main classes of tree transducers are:
Top-Down Tree Transducers (TOP).
A TOP "T" is a tuple ("Q", Σ, Γ, "I", δ) such that:
Examples of rules and intuitions on semantics.
For instance, 
is a rule – one customarily writes formula_5 instead of the pair formula_6 – and its intuitive semantics is that, under the action of "q", a tree with "f" at the root and three children is transformed into 
where, recursively, formula_8 and formula_9 are replaced, respectively, with the application of formula_10 on the first child and 
with the application of formula_11 on the third.
Semantics as term rewriting.
The semantics of each state of the transducer "T", and of "T" itself, is a binary relation between input trees (on Σ) and output trees (on Γ).
A way of defining the semantics formally is to see formula_1 as a term rewriting system, provided that in the right-hand sides the calls are written in the form formula_5, where states "q" are unary symbols. Then the semantics formula_14 of a state "q" is given by
The semantics of "T" is then defined as the union of the semantics of its initial states:
Determinism and domain.
As with tree automata, a TOP is said to be deterministic (abbreviated DTOP) if no two rules of δ share the same left-hand side, and there is at most one initial state. In that case, the semantics of the DTOP is a partial function from input trees (on Σ) to output trees (on Γ), as are the semantics of each of the DTOP's states.
The domain of a transducer is the domain of its semantics. Likewise, the image of a transducer is the image of its semantics.
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 formula_34.