Article Structure
Abstract
Hyperedge replacement grammar (HRG) is a formalism for generating and transforming graphs that has potential applications in natural language understanding and generation.
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.
Hyperedge replacement grammars
We give a short example of how HRG works, followed by formal definitions.
Parsing
Lautemann’s recognition algorithm for HRGs is a generalization of the CKY algorithm for CFGs.
Synchronous Parsing
As mentioned in Section 2.2, because HRGs have context-free derivation trees, it is easy to define synchronous HRGs, which define mappings between languages of graphs.
Conclusion
Although Lautemann’s polynomial-time extension of CKY to HRGs has been known for some time, the desire to use graph grammars for large-scale NLP applications introduces some practical considerations not accounted for in Lautemann’s original presentation.
Topics
parsing algorithm
- Just as CKY deals with substrings (i, j] of the input, the HRG parsing algorithm deals with edge-induced subgraphs I of the input.Page 3, “Parsing”
- This result, in turn, will allow us to bound the complexity of the parsing algorithm in terms of the treewidth of G.Page 6, “Parsing”
- We present the parsing algorithm as a deductive system (Shieber et al., 1995).Page 6, “Parsing”
- In the synchronous parsing algorithm , passive items have the form [A, I , X, I’, X’] and active items have the form [A —> R : R’,n,I,¢,I’,¢’].Page 8, “Synchronous Parsing”
- The complexity of the parsing algorithm is again in 0((3dn)k+1), where k is now the maximum treewidth of the dependency graph as defined in this section.Page 8, “Synchronous Parsing”
- The parsing algorithms described in this paper are implemented in the Boli-nas toolkit.3Page 8, “Conclusion”
See all papers in Proc. ACL 2013 that mention parsing algorithm.
See all papers in Proc. ACL that mention parsing algorithm.
Back to top.
binarization
- We present a more precise characterization of the algorithm’s complexity, an optimization analogous to binarization of context-free grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications.Page 1, “Abstract”
- We give a more precise complexity analysis in terms of the grammar and the size and maximum degree of the input graph, and we show how to optimize it by a process analogous to binarization of CFGs, following Gildea (2011).Page 1, “Introduction”
- In this section, we present a refinement that makes the rule-matching procedure explicit, and because it matches rules little by little, similarly to binarization of CFG rules, it does so more efliciently than the original.Page 3, “Parsing”
See all papers in Proc. ACL 2013 that mention binarization.
See all papers in Proc. ACL that mention binarization.
Back to top.
