Tree Transducer
From Cohen Courses
Jump to navigationJump to searchA 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 to
It transduces 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.