A Tree Transducer Model for Synchronous Tree-Adjoining Grammars

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

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/}
}

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
2. André Arnold and Max Dauchet. 1982. Morphismes et bimorphismes d’arbres. Theoret. Comput. Sci., 20(1):33–93. find
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
4. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. ACL, pages 263–270. Association for Computational Linguistics. find our card
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
6. Bruno Courcelle and Paul Franchi-Zannettacci. 1982. Attribute grammars and recursive program schemes. Theoret. Comput. Sci., 17:163–191, 235–257. find
7. Joost Engelfriet and Heiko Vogler. 1985. Macro tree transducers. J. Comput. System Sci., 31(1):71–146. find
8. Ferenc Gécseg and Magnus Steinby. 1984. Tree Automata. Akadémiai Kiadó, Budapest. find
9. Ferenc Gécseg and Magnus Steinby. 1997. Tree languages. In Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer. find
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 our card
11. Jonathan Graehl, Kevin Knight, and Jonathan May. 2008. Training tree transducers. Computational Linguistics, 34(3):391–427. find
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
13. Liang Huang and David Chiang. 2005. Better k-best parsing. In Proc. IWPT, pages 53–64. Association for Computational Linguistics. find
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
15. Kevin Knight. 2007. Capturing practical natural language transformations. Machine Translation, 21(2):121–133. find
16. Andreas Maletti. 2008. Compositions of extended top-down tree transducers. Inform. and Comput., 206(9– 10):1187–1196. find
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
18. Mark-Jan Nederhof. 2009. Weighted parsing of trees. In Proc. IWPT, pages 13–24. Association for Computational Linguistics. find
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
20. William C. Rounds. 1970. Mappings and grammars on trees. Math. Systems Theory, 4(3):257–287. find
21. Stuart M. Shieber and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proc. Computational Linguistics, volume 3, pages 253–258. find
22. Stuart M. Shieber. 2004. Synchronous grammars as tree transducers. In Proc. TAG+7, pages 88–95. find our card
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
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
25. James W. Thatcher. 1970. Generalized 2 sequential machine maps. J. Comput. System Sci., 4(4):339– 367. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/maletti-2010-tree-transducer-model-synchronous-tree/