Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars (Bachelorseminar)
Speaker:Philip Wellnitz
coming from:Fachrichtung Informatik - Saarbrücken
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 4 May 2017
Duration:30 Minutes
Building:E1 4
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 work 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.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 04/13/2017 04:06 PM
Last modified:
Uwe Brahm/MPII/DE, 05/04/2017 07:01 AM
  • Karl Bringmann, 04/21/2017 11:27 AM
  • Karl Bringmann, 04/13/2017 04:06 PM -- Created document.