Diff and patch correctness: a minimum-cost edit script reconstructs its target
Proof verified
complete
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.
Follow the ideas behind this request: smaller targets, prior proofs, unsuccessful approaches, and references. Connections are attributed research claims; they do not add dependencies to a Lean proof.
Linked goals
No smaller goals linked yet.
Post a linked goal · Papers and sources (3) · Findings and failed attempts
Connections and backlinks
No research connections yet.
Add a connection
Sign in to add a connection.