acl acl2010 acl2010-21 acl2010-21-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andreas Maletti
Abstract: A characterization of the expressive power of synchronous tree-adjoining grammars (STAGs) in terms of tree transducers (or equivalently, synchronous tree substitution grammars) is developed. Essentially, a STAG corresponds to an extended tree transducer that uses explicit substitution in both the input and output. This characterization allows the easy integration of STAG into toolkits for extended tree transducers. Moreover, the applicability of the characterization to several representational and algorithmic problems is demonstrated.
Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling. Pren- tice Hall. Andr e´ Arnold and Max Dauchet. 1982. Morphismes et bimorphismes d’arbres. Theoret. Comput. Sci., 20(1):33–93. 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. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. ACL, pages 263–270. Association for Computational Linguistics. David Chiang. 2006. An introduction to synchronous grammars. In Proc. ACL. Association for Computational Linguistics. Part of a tutorial given with Kevin Knight. Bruno Courcelle and Paul Franchi-Zannettacci. 1982. Attribute grammars and recursive program schemes. Theoret. Comput. Sci., 17: 163–191, 235–257. Joost Engelfriet and Heiko Vogler. 1985. Macro tree transducers. J. Comput. System Sci., 3 1(1):71–146. Ferenc G ´ecseg and Magnus Steinby. 1984. Tree Automata. Akad e´miai Kiad o´, Budapest. Ferenc G ´ecseg and Magnus Steinby. 1997. Tree languages. In Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer. Jonathan Graehl and Kevin Knight. 2004. Training tree transducers. In HLT-NAACL, pages 105–1 12. Association for Computational Linguistics. See also (Graehl et al., 2008). Jonathan Graehl, Kevin Knight, and Jonathan May. 2008. Training tree transducers. Computational Linguistics, 34(3):391–427. 1075 Jonathan Graehl, Mark Hopkins, Kevin Knight, and Andreas Maletti. 2009. The power of extended topdown tree transducers. SIAM Journal on Computing, 39(2):410–430. Liang Huang and David Chiang. 2005. Better k-best parsing. In Proc. IWPT, pages 53–64. Association for Computational Linguistics. 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. Kevin Knight. 2007. Capturing practical natural language transformations. Machine Translation, 21(2): 121–133. Andreas Maletti. 2008. Compositions of extended topdown tree transducers. Inform. and Comput., 206(9– 10): 1187–1 196. Jonathan May and Kevin Knight. 2006. TIBURON: A weighted tree automata toolkit. In Proc. CIAA, volume 4094 of LNCS, pages 102–1 13. Springer. Mark-Jan Nederhof. 2009. Weighted parsing of trees. In Proc. IWPT, pages 13–24. Association for Computational Linguistics. Rebecca Nesson, Giorgio Satta, and Stuart M. Shieber. 2008. Optimal k-arization of synchronous treeadjoining grammar. In Proc. ACL, pages 604–612. Association for Computational Linguistics. William C. Rounds. 1970. Mappings and grammars on trees. Math. Systems Theory, 4(3):257–287. Stuart M. Shieber and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proc. Computational Linguistics, volume 3, pages 253–258. Stuart M. Shieber. 2004. Synchronous grammars as tree transducers. In Proc. TAG+7, pages 88–95. Stuart M. Shieber. 2006. Unifying synchronous tree adjoining grammars and tree transducers via bimorphisms. In Proc. EACL, pages 377–384. Association for Computational Linguistics. 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. James W. Thatcher. 1970. Generalized2 sequential machine maps. J. Comput. System Sci., 4(4):339– 367. 1076