Bringmann, Karl ;
Wellnitz, Philip
CliqueBased Lower Bounds for Parsing TreeAdjoining Grammars
Abstract
Treeadjoining grammars are a generalization of contextfree grammars that are well suited to model human languages and are thus popular in computational linguistics. In the treeadjoining grammar recognition problem, given a grammar G and a string s of length n, the task is to decide whether s can be obtained from G. Rajasekaran and Yooseph’s parser (JCSS’98) solves this problem in time O(n^2w), where w < 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(G·n^6) in the case of G = Theta(n^12) would imply a breakthrough for Boolean matrix multiplication. Following an approach by Abboud et al. (FOCS’15) for contextfree grammar recognition, in this paper we resolve many of the disadvantages of the previous lower bound. We show that, even on constantsize grammars, any improvement on Rajasekaran and Yooseph’s parser would imply a breakthrough for the kClique problem. This establishes treeadjoining grammar parsing as a practically relevant problem with the unusual running time of n^2w , up to lower order factors.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs:2017:7332,
author = {Karl Bringmann and Philip Wellnitz},
title = {{CliqueBased Lower Bounds for Parsing TreeAdjoining Grammars}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {12:112:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770392},
ISSN = {18688969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7332},
URN = {urn:nbn:de:0030drops73329},
doi = {10.4230/LIPIcs.CPM.2017.12},
annote = {Keywords: conditional lower bounds, kClique, parsing, treeadjoining grammars}
}
2017
Keywords: 

conditional lower bounds, kClique, parsing, treeadjoining grammars 
Seminar: 

28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Issue date: 

2017 
Date of publication: 

2017 