bpe_full_step
def
A full Byte-Pair Encoding merge step: either the string remains unchanged, or all nonoverlapping occurrences of some pair are replaced left-to-right with a fresh symbol.
Statement
def bpe_full_step (s t : List ℕ) : Prop
- Defined in
- scout/2611-08671-greedy-byte-pair-encoding-achieves-at-least-0-361-of-the-op.md:286
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Built on 1
- bpe_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
- Used by 3
- bpe_min_greedy_utility_one_eq_optimalFor any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction…
- bpe_steps_greedy_imp_full_stepsEvery string reachable by k steps of greedy Byte-Pair Encoding merges is also reachable by k general full-merge steps.
- bpe_optimal_full_utilityThe maximum total reduction in string length achieved by any k-step sequence of full Byte-Pair Encoding merges on s.
Read back from the Lean
The definition bpe_full_step s t asserts that for lists of natural numbers s and t, either s = t, or there exist natural numbers a, b, and z such that z does not occur in s and t = bpe_full_merge a b z s.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A full Byte-Pair Encoding merge step replaces all nonoverlapping occurrences of some pair with a fresh symbol, or leaves the string unchanged. -/ def bpe_full_step (s t : List ℕ) : Prop := s = t ∨ ∃ a b z, z ∉ s ∧ t = bpe_full_merge a b z s