Tags:context free languages, edit distance, formal languages, minimal correction and term rewriting
Abstract:
We present a theory of rewriting a word into a given target language. We show that the natural notion of equivalence between cor- rections as sequences of edit operations can be captured syntactically by means of a rather simple rewrite system. Completeness relies on a normal form for corrections that is then also used to develop a notion of mini- mality for corrections. This is not based on edit distance between words and languages but on a subsequence order on corrections, capturing the intuitive notion of doing a minimal number of rewriting steps. We show that the number of minimal corrections is always finite, and that they are computable for context-free languages.
Computing All Minimal Ways to Reach a Context-Free Language