[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/maletti-2010-tree-transducer-model-synchronous-tree/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) / A Tree Transducer Model for Synchronous Tree-Adjoining Grammars

# A Tree Transducer Model for Synchronous Tree-Adjoining Grammars

**Authors:** [Andreas Maletti](https://md.mova.elamur.ai/free/en/docs/papers/authors/andreas-maletti/) · **Year:** 2010 · **Venue:** Proceedings of the 48th Annual Meeting of the ACL **Link:** [aclanthology.org/P10-1109](https://aclanthology.org/P10-1109/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**6** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/maletti-2010-tree-transducer-model-synchronous-tree/) of the 140673 papers whose bibliographies we read[Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics](https://aclanthology.org/volumes/P10-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/P10-1109/)
- [PDF](https://aclanthology.org/P10-1109.pdf)

**Authors (1)**

1. Maletti, Andreas

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## What it is about

The paper characterises the expressive power of synchronous tree-adjoining grammars (STAG) with tree transducers. A STAG is shown to correspond to an extended tree transducer that uses explicit substitution on both the input and the output side. This is equivalent to synchronous tree substitution grammar (STSG) plus adjunction rules, and the result carries over from the syntactic side to the semantic side: a STAG tree transformation can be computed by an STSG with explicit substitution. The consequence is practical. Standard problems for STAG, such as training and application, reduce to the corresponding problems for STSG, and existing STSG toolkits for extended tree transducers can be reused. The paper is formal and reports no experiments. Its main claim is the equivalence and the reduction.

## Ideas

- I1. Explicit substitution slots on meta tokens. A predicate's meta token could keep its open argument slots (the frame roles from `prag`) as explicit variables, so that the encoder fills a slot with an encoded subtree instead of re-reading the words. This is the frame-role version of open problem 1.
- I2. Modifiers as adjuncts. Adverbial phrases such as *quite often* or *in the years to come* sit outside the argument slots of the verb. Read them as adjuncts that attach to any node of a class, instead of as fixed children, and count the verses where this changes the order (open problem 4).
- I3. Use the reduction as a check on the design. If the reader's trees with explicit substitution can be expressed as STSG rules, the existing STSG algorithms apply, which lowers the cost of building new ones.

## For Mova

The code is `tools/translate` (the frame anchors in `prag` and the meta-world reader). The result is theoretical, so no number in the card is a claim about Mova. The first step is to count how many verse trees have an adverbial that changes position across the two languages, which decides whether adjunction is worth the extra machinery.

Topics: [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/topics/machine-translation/)

## Cite

The paper itself, not this card. BibTeX from the library's record of the work.

```
@inproceedings{maletti2010tree,
  title = {{A Tree Transducer Model for Synchronous Tree-Adjoining Grammars}},
  author = {Maletti, Andreas},
  booktitle = {Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://aclanthology.org/P10-1109/}
}
```

- [← previous Eurotra, history and results](https://md.mova.elamur.ai/free/en/docs/papers/maegaard-1995-eurotra-history-results/)
- [next → Why Synchronous Tree Substitution Grammars?](https://md.mova.elamur.ai/free/en/docs/papers/maletti-2010-why-synchronous-tree-substitution-grammars/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## References

25 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling. Prentice Hall. [find](https://scholar.google.com/scholar?q=Alfred+V%2E+Aho+and+Jeffrey+D%2E+Ullman%2E+1972%2E+The+Theory+of+Parsing%2C+Translation%2C+and+Compiling%2E+Prentice+Hall%2E)
2. André Arnold and Max Dauchet. 1982. Morphismes et bimorphismes d’arbres. Theoret. Comput. Sci., 20(1):33–93. [find](https://scholar.google.com/scholar?q=Andre%CC%81+Arnold+and+Max+Dauchet%2E+1982%2E+Morphismes+et+bimorphismes+d%E2%80%99arbres%2E+Theoret%2E+Comput%2E+Sci%2E%2C+20%281%29%3A33%E2%80%9393%2E)
3. Yehoshua Bar-Hillel, Micha Perles, and Eliyahu Shamir. 1964. On formal properties of simple phrase structure grammars. In Yehoshua Bar-Hillel, editor, Language and Information: Selected Essays on their Theory and Application, chapter 9, pages 116–150. Addison Wesley. [find](https://scholar.google.com/scholar?q=Yehoshua+Bar%2DHillel%2C+Micha+Perles%2C+and+Eliyahu+Shamir%2E+1964%2E+On+formal+properties+of+simple+phrase+structure+grammars%2E+In+Yehoshua+Bar%2DHillel%2C+editor%2C+Language+and+Information%3A+Selected+Essays+on+thei)
4. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. ACL, pages 263–270. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2005%2E+A+hierarchical+phrase%2Dbased+model+for+statistical+machine+translation%2E+In+Proc%2E+ACL%2C+pages+263%E2%80%93270%2E+Association+for+Computational+Linguistics%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/chiang-2005-hierarchical-phrase-based-model-statistical/)
5. David Chiang. 2006. An introduction to synchronous grammars. In Proc. ACL. Association for Computational Linguistics. Part of a tutorial given with Kevin Knight. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2006%2E+An+introduction+to+synchronous+grammars%2E+In+Proc%2E+ACL%2E+Association+for+Computational+Linguistics%2E+Part+of+a+tutorial+given+with+Kevin+Knight%2E)
6. Bruno Courcelle and Paul Franchi-Zannettacci. 1982. Attribute grammars and recursive program schemes. Theoret. Comput. Sci., 17:163–191, 235–257. [find](https://scholar.google.com/scholar?q=Bruno+Courcelle+and+Paul+Franchi%2DZannettacci%2E+1982%2E+Attribute+grammars+and+recursive+program+schemes%2E+Theoret%2E+Comput%2E+Sci%2E%2C+17%3A163%E2%80%93191%2C+235%E2%80%93257%2E)
7. Joost Engelfriet and Heiko Vogler. 1985. Macro tree transducers. J. Comput. System Sci., 31(1):71–146. [find](https://scholar.google.com/scholar?q=Joost+Engelfriet+and+Heiko+Vogler%2E+1985%2E+Macro+tree+transducers%2E+J%2E+Comput%2E+System+Sci%2E%2C+31%281%29%3A71%E2%80%93146%2E)
8. Ferenc Gécseg and Magnus Steinby. 1984. Tree Automata. Akadémiai Kiadó, Budapest. [find](https://scholar.google.com/scholar?q=Ferenc+Ge%CC%81cseg+and+Magnus+Steinby%2E+1984%2E+Tree+Automata%2E+Akade%CC%81miai+Kiado%CC%81%2C+Budapest%2E)
9. Ferenc Gécseg and Magnus Steinby. 1997. Tree languages. In Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer. [find](https://scholar.google.com/scholar?q=Ferenc+Ge%CC%81cseg+and+Magnus+Steinby%2E+1997%2E+Tree+languages%2E+In+Handbook+of+Formal+Languages%2C+volume+3%2C+chapter+1%2C+pages+1%E2%80%9368%2E+Springer%2E)
10. Jonathan Graehl and Kevin Knight. 2004. Training tree transducers. In HLT-NAACL, pages 105–112. Association for Computational Linguistics. See also (Graehl et al., 2008). [find](https://scholar.google.com/scholar?q=Jonathan+Graehl+and+Kevin+Knight%2E+2004%2E+Training+tree+transducers%2E+In+HLT%2DNAACL%2C+pages+105%E2%80%93112%2E+Association+for+Computational+Linguistics%2E+See+also+%28Graehl+et+al%2E%2C+2008%29%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/graehl-2004-training-tree-transducers/)
11. Jonathan Graehl, Kevin Knight, and Jonathan May. 2008. Training tree transducers. Computational Linguistics, 34(3):391–427. [find](https://scholar.google.com/scholar?q=Jonathan+Graehl%2C+Kevin+Knight%2C+and+Jonathan+May%2E+2008%2E+Training+tree+transducers%2E+Computational+Linguistics%2C+34%283%29%3A391%E2%80%93427%2E)
12. Jonathan Graehl, Mark Hopkins, Kevin Knight, and Andreas Maletti. 2009. The power of extended top-down tree transducers. SIAM Journal on Computing, 39(2):410–430. [find](https://scholar.google.com/scholar?q=Jonathan+Graehl%2C+Mark+Hopkins%2C+Kevin+Knight%2C+and+Andreas+Maletti%2E+2009%2E+The+power+of+extended+top%2Ddown+tree+transducers%2E+SIAM+Journal+on+Computing%2C+39%282%29%3A410%E2%80%93430%2E)
13. Liang Huang and David Chiang. 2005. Better k-best parsing. In Proc. IWPT, pages 53–64. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Liang+Huang+and+David+Chiang%2E+2005%2E+Better+k%2Dbest+parsing%2E+In+Proc%2E+IWPT%2C+pages+53%E2%80%9364%2E+Association+for+Computational+Linguistics%2E)
14. Kevin Knight and Jonathan Graehl. 2005. An overview of probabilistic tree transducers for natural language processing. In Proc. CICLing, volume 3406 of LNCS, pages 1–24. Springer. [find](https://scholar.google.com/scholar?q=Kevin+Knight+and+Jonathan+Graehl%2E+2005%2E+An+overview+of+probabilistic+tree+transducers+for+natural+language+processing%2E+In+Proc%2E+CICLing%2C+volume+3406+of+LNCS%2C+pages+1%E2%80%9324%2E+Springer%2E)
15. Kevin Knight. 2007. Capturing practical natural language transformations. Machine Translation, 21(2):121–133. [find](https://scholar.google.com/scholar?q=Kevin+Knight%2E+2007%2E+Capturing+practical+natural+language+transformations%2E+Machine+Translation%2C+21%282%29%3A121%E2%80%93133%2E)
16. Andreas Maletti. 2008. Compositions of extended top-down tree transducers. Inform. and Comput., 206(9– 10):1187–1196. [find](https://scholar.google.com/scholar?q=Andreas+Maletti%2E+2008%2E+Compositions+of+extended+top%2Ddown+tree+transducers%2E+Inform%2E+and+Comput%2E%2C+206%289%E2%80%93+10%29%3A1187%E2%80%931196%2E)
17. Jonathan May and Kevin Knight. 2006. T IBURON : A weighted tree automata toolkit. In Proc. CIAA, volume 4094 of LNCS, pages 102–113. Springer. [find](https://scholar.google.com/scholar?q=Jonathan+May+and+Kevin+Knight%2E+2006%2E+T+IBURON+%3A+A+weighted+tree+automata+toolkit%2E+In+Proc%2E+CIAA%2C+volume+4094+of+LNCS%2C+pages+102%E2%80%93113%2E+Springer%2E)
18. Mark-Jan Nederhof. 2009. Weighted parsing of trees. In Proc. IWPT, pages 13–24. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Mark%2DJan+Nederhof%2E+2009%2E+Weighted+parsing+of+trees%2E+In+Proc%2E+IWPT%2C+pages+13%E2%80%9324%2E+Association+for+Computational+Linguistics%2E)
19. Rebecca Nesson, Giorgio Satta, and Stuart M. Shieber. 2008. Optimal k-arization of synchronous tree-adjoining grammar. In Proc. ACL, pages 604–612. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Rebecca+Nesson%2C+Giorgio+Satta%2C+and+Stuart+M%2E+Shieber%2E+2008%2E+Optimal+k%2Darization+of+synchronous+tree%2Dadjoining+grammar%2E+In+Proc%2E+ACL%2C+pages+604%E2%80%93612%2E+Association+for+Computational+Linguistics%2E)
20. William C. Rounds. 1970. Mappings and grammars on trees. Math. Systems Theory, 4(3):257–287. [find](https://scholar.google.com/scholar?q=William+C%2E+Rounds%2E+1970%2E+Mappings+and+grammars+on+trees%2E+Math%2E+Systems+Theory%2C+4%283%29%3A257%E2%80%93287%2E)
21. Stuart M. Shieber and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proc. Computational Linguistics, volume 3, pages 253–258. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber+and+Yves+Schabes%2E+1990%2E+Synchronous+tree%2Dadjoining+grammars%2E+In+Proc%2E+Computational+Linguistics%2C+volume+3%2C+pages+253%E2%80%93258%2E)
22. Stuart M. Shieber. 2004. Synchronous grammars as tree transducers. In Proc. TAG+7, pages 88–95. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber%2E+2004%2E+Synchronous+grammars+as+tree+transducers%2E+In+Proc%2E+TAG%2B7%2C+pages+88%E2%80%9395%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/shieber-2004-synchronous-grammars-as-tree-transducers/)
23. Stuart M. Shieber. 2006. Unifying synchronous tree adjoining grammars and tree transducers via bimorphisms. In Proc. EACL, pages 377–384. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber%2E+2006%2E+Unifying+synchronous+tree+adjoining+grammars+and+tree+transducers+via+bimorphisms%2E+In+Proc%2E+EACL%2C+pages+377%E2%80%93384%2E+Association+for+Computational+Linguistics%2E)
24. Stuart M. Shieber. 2007. Probabilistic synchronous tree-adjoining grammars for machine translation: The argument from bilingual dictionaries. In Proc. Workshop on Syntax and Structure in Statistical Translation, pages 88–95. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber%2E+2007%2E+Probabilistic+synchronous+tree%2Dadjoining+grammars+for+machine+translation%3A+The+argument+from+bilingual+dictionaries%2E+In+Proc%2E+Workshop+on+Syntax+and+Structure+in+Statistical+T)
25. James W. Thatcher. 1970. Generalized 2 sequential machine maps. J. Comput. System Sci., 4(4):339– 367. [find](https://scholar.google.com/scholar?q=James+W%2E+Thatcher%2E+1970%2E+Generalized+2+sequential+machine+maps%2E+J%2E+Comput%2E+System+Sci%2E%2C+4%284%29%3A339%E2%80%93+367%2E)