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

DOI10.4230/LIPICS.ICALP.2017.19MaRDI QIDQ5111349zbMATH OpenOpenAlexFDO

Authors 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 programmingapproximationcontext-free grammaredit distancehardness

Mathematics Subject Classification ID

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

Recommendations

• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• Computing the Shortest String and the Edit-Distance for Parsing Expression Languages
• Computing the edit-distance between a regular language and a context-free language
• Computing the edit distance of a regular language
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• The edit-distance between a regular language and a context-free language
• Edit-distance between visibly pushdown languages
• The relative edit-distance between two input-driven languages
• Approximate membership for regular languages modulo the edit distance
• Parsing by matrix multiplication generalized to Boolean grammars

Cited in

(6)

• Clique-based lower bounds for parsing tree-adjoining grammars
• If the current clique algorithms are optimal, so is Valiant's parser
• A linear-time simulation of deterministic \(d\)-limited automata
• An error correcting parser for context free grammars that takes less than cubic time
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• 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!

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111349)