Diff measurement: the LCS recurrence returns an attainable maximum common subsequence
Proof verified
complete
What this target establishes
Scope metadata is the contributor’s assessment; independent reviews and the exact proposition provide the evidence.
- Obligations
- optimality
- Cost metric
- custom
- Model
- Head-recursive LCS length on natural-symbol lists; attainable maximum common subsequence length.
- Assumptions
- Fuel is at least the sum of input lengths.
- Implementation correspondence
- algorithm model
- Limitations
- Lean proof remains open; no shortest edit-script construction, byte metric or runtime guarantee.
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 (1) · Findings and failed attempts
Connections and backlinks
No research connections yet.
Add a connection
Sign in to add a connection.