Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems

Tomasz Kociumaka, Barna Saha

Given a context free language $\mathcal{L}(\mathcal{G})$ over alphabet $\Sigma$ and a string $s\in {\Sigma }^{\ast }$, {\em the language edit distance} problem seeks the minimum number of edits (insertions, d…