acl acl2013 acl2013-165 acl2013-165-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthias Buchse ; Alexander Koller ; Heiko Vogler
Abstract: Binarization ofgrammars is crucial for improving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter. We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.
Alfred V. Aho and Jeffrey D. Ullman. 1969. Syntax directed translations and the pushdown assembler. Journal of Computer and System Sciences, 3:37–56. Andr e´ Arnold and Max Dauchet. 1976. Bitransduction de for eˆts. In Proc. 3rd Int. Coll. Automata, Languages and Programming, pages 74–86. Edinburgh University Press. Walter S. Brainerd. 1969. Tree generating regular systems. Information and Control, 14(2):217–23 1. David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228. Steve DeNeefe and Kevin Knight. 2009. Synchronous tree-adjoining machine translation. of EMNLP, pages 727–736. In Proceedings Jason Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of the 41st ACL, pages 205–208. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of HLT/NAACL, pages 273–280. Michael Galley. 2010. GHKM rule extractor. http : / /www-nlp . st anford .edu / ˜mgal ley / s o ftware / st anford- ghkm- late st .t ar . gz, retrieved on March 28, 2012. Ferenc G ´ecseg and Magnus Steinby. 1997. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer-Verlag. Daniel Gildea. 2010. Optimal parsing strategies for linear context-free rewriting systems. In Proceedings of NAACL HLT. Joseph A. Goguen, Jim W. Thatcher, Eric G. Wagner, and Jesse B. Wright. 1977. Initial algebra semantics and continuous algebras. Journal of the ACM, 24:68–95. Carlos Gomez-Rodriguez, Marco Kuhlmann, Giorgio Satta, and David Weir. 2009. Optimal reduction of rule length in linear context-free rewriting systems. In Proceedings of NAACL HLT. Jonathan Graehl, Kevin Knight, and Jonathan May. 2008. Training tree transducers. Computational Linguistics, 34(3):391–427. Liang Huang and David Chiang. 2005. Better k-best parsing. In Proceedings of the 9th IWPT, pages 53– 64. Liang Huang, Kevin Knight, and Aravind Joshi. 2006. Statistical syntax-directed translation with extended domain of locality. In Proceedings of the 7th AMTA, pages 66–73. Liang Huang, Hao Zhang, Daniel Gildea, and Kevin Knight. 2009. Binarization of synchronous context-free grammars. Computational Linguistics, 35(4):559–595. Donald E. Knuth. 1977. A generalization of Dijkstra’s algorithm. Information Processing Letters, 6(1): 1– 5. Alexander Koller and Marco Kuhlmann. 2011. A generalized view on parsing and translation. In Proceedings of the 12th IWPT, pages 2–13. Alexander Koller and Marco Kuhlmann. 2012. Decomposing TAG algorithms using simple algebraizations. In Proceedings of the 11th TAG+ Workshop, pages 135–143. Philip M. Lewis and Richard E. Stearns. 1966. Syntax directed transduction. Foundations of Computer Science, IEEE Annual Symposium on, 0:21–35. Mark-Jan Nederhof. 2003. Weighted deductive parsing and Knuth’s algorithm. Computational Linguistics, 29(1): 135–143. Rebecca Nesson, Stuart M. Shieber, and Alexander Rush. 2006. Induction of probabilistic synchronous tree-insertion grammars for machine translation. In Proceedings of the 7th AMTA. Owen Rambow and Giorgio Satta. 1999. Independent parallelism in finite copying parallel rewriting systems. Theoretical Computer Science, 223(1–2):87– 120. David J. Weir. 1988. Characterizing Mildly ContextSensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania. Kenji Yamada and Kevin Knight. 2001. A syntaxbased statistical translation model. In Proceedings of the 39th ACL, pages 523–530. 154