Difference between revisions of "Tree Transducer"
From Cohen Courses
Jump to navigationJump to search (Created page with '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. Weighted tree tra…') |
|||
| Line 1: | Line 1: | ||
| − | 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. | + | 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 == | == Definition == | ||
| + | A nondeterministic top-down tree transducer is a tuple [[File:TreeTransducerTuple.png]] where | ||
| + | [[File:TreeTransducerDef.png]] | ||
| + | |||
| + | ([[File:TreeTransducersXn.png]] is n numerically ordered variables.) | ||
== Examples == | == Examples == | ||
| + | The following example changes subtrees of the form <math>f(t_1,f(t_2,t_3))</math> to <math>f(f(t_1,t_2),t_3)</math> | ||
| + | |||
| + | [[File:TreeTransducerExample.png]] | ||
| + | |||
| + | It transduces <math>f(f(a,f(b,a)),f(a,b)) into f(f(f(f(a,b),a),a),b)</math> as shown in the derivation and figure below. | ||
| + | |||
| + | [[File:TreeTransducerExampleDerivation.png]] | ||
| + | |||
| + | [[File:TreeTransducerExampleFigure.png]] | ||
| + | |||
| + | == Papers == | ||
| + | The definition and example given here are from [http://www.cs.rutgers.edu/TAG+7/papers/shieber.pdf 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.] | ||
Latest revision as of 04:59, 10 November 2011
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 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.
