AFTD Auto-Formalizing Theoretical Domains

string_overlap_len_sanity

theoremverified

ov(123,234) = 23, ov(11,11) = 1, ov(12,12) is empty.

Statement

theorem string_overlap_len_sanity :
    string_overlap_len [1, 2, 3] [2, 3, 4] = 2 ∧ string_overlap_len [1, 1] [1, 1] = 1 ∧
      string_overlap_len [1, 2] [1, 2] = 0
Source
Sanity check of string_overlap_len (arXiv:2611.16573)
Verified
14 Nov 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • string_overlap_lenFor two lists x, y : List Γ over an arbitrary alphabet type Γ with decidable equality (strings are lists of letters, not Lean Strings),…

The proof, explained

The theorem verifies three concrete evaluations of the string overlap length function on short integer lists. Because the function is defined as a bounded search over finite lists with decidable equality, the entire proposition is decidable by finite evaluation. The proof delegates the calculation directly to the `decide` tactic.

  1. The overlap length is 2 for [1, 2, 3] and [2, 3, 4], 1 for [1, 1] and [1, 1], and 0 for [1, 2] and [1, 2]. automation

    The function `string_overlap_len x y` searches for the largest integer k < min(|x|, |y|) such that the suffix of x of length k equals the prefix of y of length k. For these explicit lists, checking the condition requires testing only k ∈ {0, 1, 2}: - For [1, 2, 3] and [2, 3, 4], the suffix [2, 3] equals the prefix [2, 3], giving overlap 2. - For [1, 1] and [1, 1], the strict inequality restricts to k < 2, and the length-1 suffix [1] matches the length-1 prefix [1], giving overlap 1. - For [1, 2] and [1, 2], k < 2 requires checking k = 1 where [2] ≠ [1], leaving only the empty overlap k = 0. The `decide` tactic evaluates this bounded search directly by computation to close the goal.

    line 3

          string_overlap_len [1, 2] [1, 2] = 0 := 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_len_sanity :    string_overlap_len [1, 2, 3] [2, 3, 4] = 2 ∧ string_overlap_len [1, 1] [1, 1] = 1 ∧      string_overlap_len [1, 2] [1, 2] = 0 := by decide
See it in the graphDiscuss this resultChallenge it