  We study tree-to-tree transformations that can be defined in first-order
logic or monadic second-order logic. We prove a decomposition theorem, which
shows that every transformation can be obtained from prime transformations,
such as tree-to-tree homomorphisms or pre-order traversal, by using combinators
such as function composition.
