Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!

DOI10.4230/LIPIcs.ICALP.2017.19zbMath1441.68114OpenAlexW2739492694MaRDI QIDQ5111349

Rajesh Jayaram, Barna Saha

Publication date: 27 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7454/pdf/LIPIcs-ICALP-2017-19.pdf/

zbMATH Keywords

dynamic programmingapproximationhardnesscontext-free grammaredit distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (2)

A linear-time simulation of deterministic \(d\)-limited automata ⋮ Absent Subsequences in Words

This page was built for publication: Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!