Tree transducer

A tree transducer is a finite state machine taking as input a tree structure, 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 finite-state transducers extend finite-state automata.