AFTD Auto-Formalizing Theoretical Domains

bpe_partial_merge_can_skip_overlap

theoremverified

A partial merge of equal adjacent symbols may skip the first occurrence and merge the overlapping middle occurrence.

Statement

theorem bpe_partial_merge_can_skip_overlap : bpe_partial_merge 1 1 9 [1,1,1,1] [1,9,1]
Source
Sanity check for the partial merge relation in OP-1288.
Verified
10 Nov 2026
Axioms
Quot.soundpropext
Built on 1
  • bpe_partial_mergeThe relation between input and output strings obtained by replacing an arbitrary subset of pairwise nonoverlapping occurrences of the…

The proof, explained

The theorem shows that byte-pair encoding (BPE) partial merge can skip an initial match to merge an overlapping pair: replacing (1, 1) with 9 can turn [1, 1, 1, 1] into [1, 9, 1]. The proof unfolds the recursive definition of `bpe_partial_merge` using `simp`, which evaluates the choices on concrete lists and confirms the valid merge path.

  1. The list [1, 9, 1] is a valid partial merge of the pair (1, 1) into 9 on the input [1, 1, 1, 1]. automation

    By unfolding the recursive definition of bpe_partial_merge on concrete lists, the simplifier confirms that [1, 1, 1, 1] can step to [1, 9, 1]: the first symbol 1 is skipped, the next pair (1, 1) is merged into 9, and the remaining singleton [1] is kept by the base case.

    line 1

    uses bpe_partial_merge

    theorem bpe_partial_merge_can_skip_overlap : bpe_partial_merge 1 1 9 [1,1,1,1] [1,9,1] := by simp [bpe_partial_merge]
bpe_partial_merge
A relation specifying that the second list is obtained from the first by nondeterministically merging occurrences of adjacent pairs (a, b) into z, or leaving symbols unmerged.

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 bpe_partial_merge_can_skip_overlap : bpe_partial_merge 1 1 9 [1,1,1,1] [1,9,1] := by simp [bpe_partial_merge]
See it in the graphDiscuss this resultChallenge it