AFTD Auto-Formalizing Theoretical Domains

string_overlap_merge_sanity

theoremverified

⟨123, 234⟩ = 1234.

Statement

theorem string_overlap_merge_sanity :
    string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4]
Source
Sanity check of string_overlap_merge (arXiv:2611.16573)
Verified
14 Nov 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • string_overlap_mergeFor two lists x, y : List Γ over an alphabet type Γ with decidable equality, the overlap merge ⟨x,y⟩ is the list consisting of the first…

The proof, explained

The theorem verifies as a sanity check that merging the lists `[1, 2, 3]` and `[2, 3, 4]` yields `[1, 2, 3, 4]`. Because the inputs are concrete lists and all functions involved are fully computable, the statement is proved by direct computation using the `decide` tactic.

  1. string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4] automation

    Both lists and all operations in `string_overlap_merge`—length calculation, bounded linear search for the greatest overlap length, list dropping, taking, and concatenation—are computable for concrete lists of natural numbers. The maximal proper overlap between `[1, 2, 3]` and `[2, 3, 4]` is `[2, 3]` (length 2), so the first list is trimmed to its first `3 - 2 = 1` element (`[1]`) and concatenated with `[2, 3, 4]`, yielding `[1, 2, 3, 4]`. The `decide` tactic performs this finite computation directly to close the goal.

    line 2

        string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4] := by decide

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem string_overlap_merge_sanity :    string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4] := by decide
See it in the graphDiscuss this resultChallenge it