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

DOI10.4230/LIPICS.ICALP.2017.19zbMATH Open1441.68114OpenAlexW2739492694MaRDI QIDQ5111349FDOQ5111349

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)

Cited In (2)

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

   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 👍 👎

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)