Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars
详细信息 查看全文
- 作者：Matthias Büchse (1) matthias.buechse@tu-dresden.de
Andreas Maletti (2) andreas.maletti@ims.uni-stuttgart.de
Heiko Vogler (1) heiko.vogler@tu-dresden.de - 刊名：Lecture Notes in Computer Science
- 出版年：2012
- 出版时间：2012
- 年：2012
- 卷：7410
- 期：1
- 页码：368-379
- 全文大小：258.2 KB
- 参考文献：1. Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling. Prentice Hall (1972)
2. Büchse, M., Nederhof, M.J., Vogler, H.: Tree parsing with synchronous tree-adjoining grammars. In: Proc. Parsing Technologies, pp. 14–25. ACL (2011)
3. Büchse, M., Nederhof, M.J., Vogler, H.: Tree parsing for tree-adjoining machine translation (submitted, 2012), www.inf.tu-dresden.de/index.php?node_id=1571
4. Chiang, D.: Hierarchical phrase-based translation. Comput. Linguist. 33(2), 201–228 (2007)
5. Courcelle, B., Franchi-Zannettacci, P.: Attribute grammars and recursive program schemes I. Theoret. Comput. Sci. 17(2), 163–191 (1982)
6. DeNeefe, S.: Tree-Adjoining Machine Translation. Ph.D. thesis, University of Southern California (2011)
7. DeNeefe, S., Knight, K., Vogler, H.: A decoder for probabilistic synchronous tree insertion grammars. In: Proc. Applications of Tree Automata in Natural Language Processing, pp. 10–18. ACL (2010)
8. Engelfriet, J.: Bottom-up and top-down tree transformations—a comparison. Math. Systems Theory 9(3), 198–231 (1975)
9. Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. In: Book, R.V. (ed.) Formal Language Theory—Perspectives and Open Problems, pp. 241–286. Academic Press (1980)
10. Engelfriet, J., Vogler, H.: Macro tree transducers. J. Comput. System Sci. 31(1), 71–146 (1985)
11. Fül?p, Z., Maletti, A., Vogler, H.: Preservation of recognizability for synchronous tree substitution grammars. In: Proc. Applications of Tree Automata in Natural Language Processing, pp. 1–9. ACL (2010)
12. Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984)
13. Gécseg, F., Steinby, M.: Tree languages. In: Rozenberg and Salomaa [23], ch. 1, pp. 1–68
14. Graehl, J., Knight, K., May, J.: Training tree transducers. Comput. Linguist. 34(3), 391–427 (2008)
15. Joshi, A., Schabes, Y.: Tree-adjoining grammars. In: Rozenberg and Salomaa [23], ch. 2, pp. 69–123
16. Knight, K., Graehl, J.: An Overview of Probabilistic Tree Transducers for Natural Language Processing. In: Gelbukh, A. (ed.) CICLing 2005. LNCS, vol. 3406, pp. 1–24. Springer, Heidelberg (2005)
17. Koehn, P.: Statistical Machine Translation. Cambridge University Press (2010)
18. Maletti, A.: Compositions of extended top-down tree transducers. Inform. and Comput. 206(9-10), 1187–1196 (2008)
19. Maletti, A.: A tree transducer model for synchronous tree-adjoining grammars. In: Proc. Association for Computational Linguistics, pp. 1067–1076. ACL (2010)
20. Maletti, A., Engelfriet, J.: Strong lexicalization of tree adjoining grammars. In: Proc. Association for Computational Linguistics. ACL (to appear, 2012)
21. Nesson, R., Shieber, S.M., Rush, A.: Induction of probabilistic synchronous tree-insertion grammars for machine translation. In: Proc. Association for Machine Translation in the Americas (2006)
22. Rounds, W.C.: Mappings and grammars on trees. Math. Systems Theory 4(3), 257–287 (1970)
23. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 3. Springer (1997)
24. Schabes, Y.: Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia (1990)
25. Shieber, S.M.: Synchronous grammars as tree transducers. In: Proc. Tree Adjoining Grammar and Related Formalisms, pp. 88–95 (2004)
26. Shieber, S.M.: Unifying synchronous tree adjoining grammars and tree transducers via bimorphisms. In: Proc. European Chapter of the Association for Computational Linguistics, pp. 377–384. ACL (2006)
27. Shieber, S.M.: Probabilistic synchronous tree-adjoining grammars for machine translation: The argument from bilingual dictionaries. In: Proc. Syntax and Structure in Statistical Translation, pp. 88–95. ACL (2007)
28. Shieber, S.M., Schabes, Y.: Synchronous tree-adjoining grammars. In: Proc. Computational Linguistics, pp. 253–258. University of Helsinki (1990)
29. Thatcher, J.W.: Generalized2 sequential machine maps. J. Comput. System Sci. 4(4), 339–367 (1970)
30. The XTAG Project, www.cis.upenn.edu/~xtag/ - 作者单位：1. Department of Computer Science, Technische Universit?t Dresden, 01062 Dresden, Germany2. Institute for Natural Language Processing, Universit?t Stuttgart, Pfaffenwaldring 5b, 70569 Stuttgart, Germany
- ISSN：1611-3349
文摘
Synchronous tree-adjoining grammars have been given two types of semantics: one based on bimorphisms and one based on synchronous derivations, in both of which the input and output trees are constructed synchronously. We introduce a third type of semantics that is based on unidirectional derivations. It derives output trees based on a given input tree and thus marks a first step towards conditional probability distributions. We prove that the unidirectional semantics coincides with the bimorphism-based semantics with the help of a strong correspondence to linear and nondeleting extended top-down tree transducers with explicit substitution. In addition, we show that stateful synchronous tree-adjoining grammars admit a normal form in which only adjunction is used. This contrasts the situation encountered in the stateless case.