Parsing Graphs with Hyperedge Replacement Grammars

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 924–932, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Parsing Graphs with Hyperedge Replacement Grammars David Chiang Information Sciences Institute University of Southern California Jacob Andreas Columbia University University of Cambridge Daniel Bauer Department of Computer Science Columbia University Karl Moritz Hermann Department of Computer Science University of Oxford Bevan Jones University of Edinburgh Macquarie University Kevin Knight Information Sciences Institute University of Southern California Abstract Hyperedge replacement grammar (HRG) is a formalism for generating and trans- forming graphs that has potential appli- cations in natural language understand- ing and generation. A recognition al- gorithm 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 optimiza- tion analogous to binarization of context- free grammars, and some important im- plementation details, resulting in an algo- rithm that is practical for natural-language applications. The algorithm is part of Boli- nas, a new software toolkit for HRG pro- cessing. 1 Introduction Hyperedge replacement grammar (HRG) is a context-free rewriting formalism for generating graphs (Drewes et al., 1997), and its synchronous counterpart can be used for transforming graphs to/from other graphs or trees. As such, it has great potential for applications in natural language un- derstanding and generation, and semantics-based machine translation (Jones et al., 2012). Fig- ure 1 shows some examples of graphs for natural- language semantics. A polynomial-time recognition algorithm for HRGs was described by Lautemann (1990), build- ing on the work of Rozenberg and Welzl (1986) on boundary node label controlled grammars, and others have presented polynomial-time algorithms as well (Mazanek and Minas, 2008; Moot, 2008). Although Lautemann’s algorithm is correct and tractable, its presentation is prefaced with the re- mark: “As we are only interested in distinguish- ing polynomial time from non-polynomial time, the analysis will be rather crude, and implemen- tation details will be explicated as little as possi- ble.” Indeed, the key step of the algorithm, which matches a rule against the input graph, is described at a very high level, so that it is not obvious (for a non-expert in graph algorithms) how to implement it. More importantly, this step as described leads to a time complexity that is polynomial, but poten- tially of very high degree. In this paper, we describe in detail a more effi- cient version of this algorithm and its implementa- tion. We give a more precise complexity analysis in terms of the grammar and the size and maxi- mum degree of the input graph, and we show how to optimize it by a process analogous to binariza- tion of CFGs, following Gildea (2011). The re- sulting algorithm is practical and is implemented as part of the open-source Bolinas toolkit for hy- peredge replacement grammars. 2 Hyperedge replacement grammars We give a short example of how HRG works, fol- lowed by formal definitions. 2.1 Example Consider a weighted graph language …

Content truncated to 500 words