Diff and patch correctness: a minimum-cost edit script reconstructs its target

What this target establishes

Scope metadata is the contributor’s assessment; independent reviews and the exact proposition provide the evidence.

Obligations

round trip, optimality

Cost metric

edit count

Model

Partial unit-cost Levenshtein script application and recursive minimum-cost candidate selection.

Assumptions

Fuel is at least the sum of input lengths. Copy costs zero; replace, delete and insert each cost one.

Implementation correspondence

algorithm model

Limitations

Lean proof remains open; source-consuming operations reject empty input. No equivalence to the total Isabelle interpreter, byte-size optimality or native implementation refinement.