bpe_partial_merge
def
The relation between input and output strings obtained by replacing an arbitrary subset of pairwise nonoverlapping occurrences of the given pair by the given symbol.
Statement
def bpe_partial_merge (a b z : ℕ) : List ℕ → List ℕ → Prop
- Source
- Definitions for OP-1288, following arXiv:2611.08671, Section 2.
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Used by 4
- bpe_partial_stepA partial merge replaces an arbitrary nonoverlapping subset of one pair by a fresh symbol, with an unchanged step allowed.
- bpe_partial_merge_disallows_overlapsTwo overlapping adjacent occurrences in a three-symbol run cannot both be merged.
- bpe_partial_merge_can_skip_overlapA partial merge of equal adjacent symbols may skip the first occurrence and merge the overlapping middle occurrence.
- bpe_worst_case_ratio_three_upper_boundThe worst-case ratio of greedy Byte-Pair Encoding to optimal partial-merge utility for three merges is at most 7/12.
Lean source view module on GitHub
def bpe_partial_merge (a b z : ℕ) : List ℕ → List ℕ → Prop | [], t => t = [] | [x], t => t = [x] | x :: y :: xs, t => (∃ out, t = x :: out ∧ bpe_partial_merge a b z (y :: xs) out) ∨ (x = a ∧ y = b ∧ ∃ out, t = z :: out ∧ bpe_partial_merge a b z xs out)