Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
复制标题
用于解析树相邻语法的基于派系的下界
DOI：
10.4230/lipics.cpm.2017.12
复制
发表时间：
2018
影响因子：
0.1
通讯作者：
Philip Wellnitz
中科院分区：
文献类型：
--
作者：
K. Bringmann;Philip Wellnitz
树邻接文法是上下文无关文法的一种推广，它非常适合于模拟人类语言，因此在计算语言学中很受欢迎。在树邻接文法识别问题中，给定一个文法$\Gamma$和一个长度为$n$的字符串$s$，任务是判断$s$是否可以从$\Gamma$得到。Rajasekaran和Yooseph的解析器（JCSS'98）在时间上解决了这个问题，其中$\omega < 2.373$是矩阵乘法指数。时间复杂度为O（n^6）$。
第一个关于硬度的证据是由Satta（J. Comp. Linguist. '94）：对于更一般的解析问题，任何避免快速矩阵乘法并且明显快于$O（|伽马射线|n^6）$在$的情况下|伽马射线|= \Theta（n^{12}）$将意味着布尔矩阵乘法的突破。
遵循Abboud等人的方法。（FOCS'15）上下文无关的语法识别，在本文中，我们解决了许多以前的下界的缺点。我们表明，即使在恒定大小的语法，任何Rajasekaran和Yooseph的解析器的改进将意味着突破的$k$-团的问题。这建立了树邻接语法分析作为一个实际相关的问题，不寻常的运行时间为$n^{2\omega}$，直到低阶因子。
Tree-adjoining grammars are a generalization of context-free grammars that are well suited to model human languages and are thus popular in computational linguistics. In the tree-adjoining grammar recognition problem, given a grammar $\Gamma$ and a string $s$ of length $n$, the task is to decide whether $s$ can be obtained from $\Gamma$. Rajasekaran and Yooseph's parser (JCSS'98) solves this problem in time $O(n^{2\omega})$, where $\omega < 2.373$ is the matrix multiplication exponent. The best algorithms avoiding fast matrix multiplication take time $O(n^6)$.
The first evidence for hardness was given by Satta (J. Comp. Linguist.'94): For a more general parsing problem, any algorithm that avoids fast matrix multiplication and is significantly faster than $O(|\Gamma| n^6)$ in the case of $|\Gamma| = \Theta(n^{12})$ would imply a breakthrough for Boolean matrix multiplication.
Following an approach by Abboud et al. (FOCS'15) for context-free grammar recognition, in this paper we resolve many of the disadvantages of the previous lower bound. We show that, even on constant-size grammars, any improvement on Rajasekaran and Yooseph's parser would imply a breakthrough for the $k$-Clique problem. This establishes tree-adjoining grammar parsing as a practically relevant problem with the unusual running time of $n^{2\omega}$, up to lower order factors.
使用心理语言驱动的树邻接语法进行增量预测解析
影响因子：
9.3
作者：
V. Demberg;F. Keller;A. Koller
通讯作者：
A. Koller