AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it