Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
DOI10.4230/LIPICS.ICALP.2017.19zbMATH Open1441.68114OpenAlexW2739492694MaRDI QIDQ5111349FDOQ5111349
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/
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
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 (5)
- A linear-time simulation of deterministic \(d\)-limited automata
- An error correcting parser for context free grammars that takes less than cubic time
- Clique-based lower bounds for parsing tree-adjoining grammars
- If the current clique algorithms are optimal, so is Valiant's parser
- 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)
