Tree Transducer

From Cohen Courses
Jump to navigationJump to search

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 TreeTransducerTuple.png where

TreeTransducerDef.png

(TreeTransducersXn.png is n numerically ordered variables.)

Examples

The following example changes subtrees of the form to

TreeTransducerExample.png

It transduces as shown in the derivation and figure below.

TreeTransducerExampleDerivation.png

TreeTransducerExampleFigure.png

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.