| ||||
| ||||
![]() Title:Computing All Minimal Ways to Reach a Context-Free Language Conference:RP24 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 ![]() Computing All Minimal Ways to Reach a Context-Free Language | ||||
Copyright © 2002 – 2025 EasyChair |