acl acl2013 acl2013-274 acl2013-274-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David Chiang ; Jacob Andreas ; Daniel Bauer ; Karl Moritz Hermann ; Bevan Jones ; Kevin Knight
Abstract: Hyperedge replacement grammar (HRG) is a formalism for generating and transforming graphs that has potential applications in natural language understanding and generation. A recognition algorithm due to Lautemann is known to be polynomial-time for graphs that are connected and of bounded degree. We present a more precise characterization of the algorithm’s complexity, an optimization analogous to binarization of contextfree grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications. The algorithm is part of Bolinas, a new software toolkit for HRG processing.
Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. 1987. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods, 8(2). Hans L. Bodlaender. 1997. Treewidth: Algorithmic techniques and results. In Proc. 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS ’97), pages 29–36, Berlin. Springer-Verlag. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011. Solving connectivity problems parameterized by treewidth in single exponential time. Computing Research Repository, abs/1 103.0534. Frank Drewes, Hans-J¨ org Kreowski, and Annegret Habel. 1997. Hyperedge replacement graph grammars. In Grzegorz Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformation, pages 95–162. World Scientific. Daniel Gildea. 2011. tree decomposition. 37(1):231–248. Grammar factorization by Computational Linguistics, Vibhav Gogate and Rina Dechter. 2004. A complete anytime algorithm for treewidth. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. Bevan Jones, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, and Kevin Knight. 2012. Semantics-based machine translation with hyperedge replacement grammars. In Proc. COLING. Aravind K. Joshi and Yves Schabes. 1997. Treeadjoining grammars. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages and Automata, volume 3, pages 69–124. Springer. Clemens Lautemann. 1990. The complexity of graph languages generated by hyperedge replacement. Acta Informatica, 27:399–421. Steffen Mazanek and Mark Minas. 2008. Parsing of hyperedge replacement grammars with graph parser combinators. In Proc. 7th International Workshop on Graph Transformation and Visual Modeling Techniques. Richard Moot. 2008. Lambek grammars, tree adjoining grammars and hyperedge replacement grammars. In Proc. TAG+9, pages 65–72. Grzegorz Rozenberg and Emo Welzl. 1986. Boundary NLC graph grammars—basic definitions, normal forms, and complexity. Information and Control, 69: 136–167. Stuart M. Shieber, Yves Schabes, and Fernando C. N. Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24:3–36. Lappoon Tang and Raymond Mooney. 2001. Using multiple clause constructors in inductive logic programming for semantic parsing. In Proc. European Conference on Machine Learning. 932