Ordered Tree Decomposition for HRG Rule Extraction
Ordered Tree Decomposition for HRG Rule Extraction
复制标题
HRG 规则提取的有序树分解
DOI：
10.1162/coli_a_00350
复制
发表时间：
2019
影响因子：
9.3
通讯作者：
Peng, Xiaochang
中科院分区：
文献类型：
--
作者：
Gildea, Daniel;Satta, Giorgio;Peng, Xiaochang
我们提出了一种从带有顶点顺序的图中提取超边缘替换语法（Hyperedge Replacement Grammar， HRG）规则的算法。我们的算法是基于找到相对于顶点顺序的最小宽度的树分解，然后为该结构中的每个节点提取一条规则。输入图的顶点的固定顺序的假设使得在多项式时间内解决问题成为可能，这与为图找到最优树分解的问题是np困难的事实形成对比。我们还提出了基于hrg的多项式时间解析算法，其中输入是一个顶点序列，输出是一个图结构。我们的算法的预期应用是自然语言的语义表示的语法提取和解析。我们将我们的算法应用于带有抽象意义表示注释的数据，并报告结果语法的特征。
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 and report on the characteristics of the resulting grammars.
登录
查看更多内容
一般上下文无关语言的解析
DOI：
--
发表时间：
1976
期刊：
Advances in Computing
影响因子：
--
作者：
S. Graham;M. Harrison
通讯作者：
M. Harrison
DOI：
--
发表时间：
1988
期刊：
Colloquium on Trees in Algebra and Programming
影响因子：
--
作者：
C. Lautemann
通讯作者：
C. Lautemann
使用通过树分解提取的语法对图语言进行建模
DOI：
--
发表时间：
2013
期刊：
Finite-State Methods and Natural Language Processing
影响因子：
--
作者：
Bevan K. Jones;S. Goldwater;Mark Johnson
通讯作者：
Mark Johnson
进退两难——超边替换 DAG 语法的统一解析
DOI：
--
发表时间：
2016
期刊：
Language and Automata Theory and Applications
影响因子：
--
作者：
Henrik Björklund;F. Drewes;Petter Ericson
通讯作者：
Petter Ericson
表格解析
DOI：
--
发表时间：
2004
期刊：
arXiv.org
影响因子：
--
作者：
M. Nederhof;G. Satta
通讯作者：
G. Satta