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 such 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 report some experiments based on Abstract Meaning Representations.