English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars

Bringmann, K., & Wellnitz, P. (2018). Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. Retrieved from http://arxiv.org/abs/1803.00804.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0001-3E2A-C Version Permalink: http://hdl.handle.net/21.11116/0000-0001-3E2B-B
Genre: Paper

Files

show Files
hide Files
:
arXiv:1803.00804.pdf (Preprint), 232KB
Name:
arXiv:1803.00804.pdf
Description:
File downloaded from arXiv at 2018-05-03 10:21 Presented at CPM'17. 15 pages
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Bringmann, Karl1, Author              
Wellnitz, Philip2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2018-03-022018
 Publication Status: Published online
 Pages: 15 p.
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: arXiv: 1803.00804
URI: http://arxiv.org/abs/1803.00804
BibTex Citekey: Bringmann_arXiv1803.00804
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show