Fact 7.6 — a common last or first character does not change the edit distance
OpenDynApproxIdx.Main.fact_7_6approximate-pattern-matchingedit-distancep2o-gran-per-chapterp2o-plan-paperp2o-v1string-algorithms
For strings and a character , appending to both or prepending to both leaves the edit distance unchanged:
Here is the edit distance (minimum number of character insertions, deletions and substitutions). The fact is used in the proof of Lemma 7.8 to split an alignment at exactly matched characters.
Differences from the source:
- encoding: strings over the integer alphabet Σ, 0-based positions; δ_E the minimum number of insertions, deletions and substitutions → List ℕ; PMEdits.Main.ed, the minimum cost of an alignment-graph path from (0,0) to (|U|,|V|); reason: the standard bijection between edit sequences and alignment-graph paths; same values
Preamble
import Mathlib import Definitions.Def_PMEdits_Main_Strings
Formal statement
namespace DynApproxIdx.Main
open PMEdits.Main
/-- **Fact 7.6** (Charalampopoulos, Ellert, Radoszewski, *Dynamic Approximate Text Indexing*, STOC
2027 submission, p. 32 (PDF 34)). For any two strings `A` and `B` and character `c`,
`δ_E(Ac, Bc) = δ_E(A, B) = δ_E(cA, cB)`. -/
theorem fact_7_6 (A B : List ℕ) (c : ℕ) :
ed (A ++ [c]) (B ++ [c]) = ed A B ∧ ed A B = ed (c :: A) (c :: B) := by sorry
end DynApproxIdx.Main
Source
Charalampopoulos, Ellert, Radoszewski, Dynamic Approximate Text Indexing, STOC 2027 submission (manuscript sha256 7f902057…), p. 32 (PDF 34), Fact 7.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.