2026-07-21T14:16:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7332 2024-03-06T10:40:07Z ddc:004 open_access

Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars Bringmann, Karl Wellnitz, Philip conditional lower bounds k-Clique parsing tree-adjoining grammars 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 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 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^2w , up to lower order factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karl Bringmann and Philip Wellnitz 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.12 urn:nbn:de:0030-drops-73329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.12 eng https://creativecommons.org/licenses/by/3.0/legalcode