Tree Transducer

A tree transducer takes a tree as input and produces another tree. It is similar to a finite state transducer (FST) but operates on trees rather than strings. Tree transducers are commonly used in machine translation.

Definition

A nondeterministic top-down tree transducer is a tuple where

( is n numerically ordered variables.)

Examples

The following example changes subtrees of the form $f(t_{1},f(t_{2},t_{3}))$ to $f(f(t_{1},t_{2}),t_{3})$

It transduces $f(f(a,f(b,a)),f(a,b))intof(f(f(f(a,b),a),a),b)$ as shown in the derivation and figure below.

Papers

The definition and example given here are from Stuart M. Shieber. Synchronous grammars as tree transducers. Proceedings of the Seventh International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+ 7), Vancouver, Canada, May 20-22 2004.