Editing Edit distance (section)

== Language edit distance ==
A generalization of the edit distance between strings is the language edit distance between a string and a language, usually a [[formal language]]. Instead of considering the edit distance between one string and another, the language edit distance is the minimum edit distance that can be attained between a fixed string and ''any'' string taken from a set of strings. More formally, for any language ''L'' and string ''x'' over an alphabet {{math|Σ}}, the ''language edit distance'' d(''L'', ''x'') is given by<ref name=":0">{{cite book|doi=10.1109/focs.2016.48|chapter=Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product|chapter-url=https://theory.stanford.edu/~virgi/RNAfold.pdf|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|pages=375–384|year=2016|last1=Bringmann|first1=Karl|last2=Grandoni|first2=Fabrizio|last3=Saha|first3=Barna|author3-link=Barna Saha|last4=Williams|first4=Virginia Vassilevska|author-link4=Virginia Vassilevska Williams|isbn=978-1-5090-3933-3|arxiv=1707.05095|s2cid=17064578 }}</ref><math>d(L,x) = \min_{y \in L} d(x,y)

</math>, where <math>d(x,y)</math> is the string edit distance. When the language ''L'' is [[Context-free language|context free]], there is a cubic time dynamic programming algorithm proposed by Aho and Peterson in 1972 which computes the language edit distance.<ref>{{Cite journal|last1=Aho|first1=A.|last2=Peterson|first2=T.|date=1972-12-01|title=A Minimum Distance Error-Correcting Parser for Context-Free Languages|journal=SIAM Journal on Computing|volume=1|issue=4|pages=305–312|doi=10.1137/0201022|issn=0097-5397}}</ref> For less expressive families of grammars, such as the [[regular grammar]]s, faster algorithms exist for computing the edit distance.<ref>{{cite journal|doi=10.1145/360980.360995|title=Order-n correction for regular languages|journal=Communications of the ACM|volume=17|issue=5|pages=265–268|year=1974|last1=Wagner|first1=Robert A.|s2cid=11063282|doi-access=free}}</ref>

Language edit distance has found many diverse applications, such as RNA folding, error correction, and solutions to the Optimum Stack Generation problem.<ref name=":0" /><ref>{{Cite conference|last=Saha|first=B.|author-link=Barna Saha|s2cid=14806359|date=2014-10-01|title=The Dyck Language Edit Distance Problem in Near-Linear Time|conference=2014 IEEE 55th Annual Symposium on Foundations of Computer Science|pages=611–620|doi=10.1109/FOCS.2014.71|isbn=978-1-4799-6517-5}}</ref>