Paper Info
Title
Ordered Tree Decomposition for HRG Rule Extraction
Abstract
We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the problem of finding optimal tree decompositions for a graph is NP-hard. We also present polynomial-time algorithms for parsing based on our HRGs, where the input is a vertex sequence and the output is a graph structure. The intended application of our algorithms is grammar extraction and parsing for semantic representation of natural language. We apply our algorithms to data annotated with Abstract Meaning Representations (AMRs) and report on the characteristics of the resulting grammars.
Year
DOI
Venue
2019
10.1162/coli_a_00350
Computational Linguistics
Field
DocType
Volume
Graph,Vertex (geometry),Computer science,Tree decomposition,Grammar,Theoretical computer science,Artificial intelligence,Natural language processing
Journal
45
Issue
ISSN
Citations 
2
0891-2017
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Daniel Gildea12269193.43
Giorgio Satta290290.85
Xiaochang Peng3545.31