AFTD Auto-Formalizing Theoretical Domains

bpe_greedy_run

def

The relation defining a k-step greedy Byte-Pair Encoding run on string s yielding string t: for k = 0 we have s = t, and for k + 1 there exists an intermediate string u such that bpe_greedy_run k s u and bpe_greedy_step_with (k + 2) u t.

Statement

def bpe_greedy_run : ℕ → List ℕ → List ℕ → Prop
Defined in
Sennrich, Haddow, Birch, arXiv:1508.07909; Gage, C Users Journal 1994
Verified
12 Nov 2026
Axioms
none listed
Built on 1
  • bpe_greedy_step_withA greedy full Byte-Pair Encoding merge step with fresh symbol z: either no adjacent pair occurs with positive count in string s and t = s,…
Used by 4
  • bpe_deviation_probGiven parameters (p : ℝ), hypothesis (hp : 0 < p ∧ p < 1), (k N : ℕ), and (c ε : ℝ), bpe_deviation_prob p hp k N c ε is the real number…
  • bpe_greedy_run_length_lower_boundApplying k greedy full BPE merges reduces the string length by at most a factor of 2^k: if bpe_greedy_run k s t, then s.length ≤ 2^k *…
  • bpe_deviation_prob_nonnegFor any source bias p ∈ (0, 1), step count k, input length N, target constant c, and tolerance ε, the deviation probability…
  • bpe_zero_step_run_uniqueA zero-step greedy Byte-Pair Encoding run from string s to string t holds if and only if s = t.

Read back from the Lean

bpe_greedy_run n s t is a recursively defined relation asserting that the list of natural numbers t can be obtained from s after n steps of greedy byte-pair encoding (BPE). - Base case (n = 0): s = t. - Inductive step (n = k + 1): there exists an intermediate list u : List ℕ such that bpe_greedy_run k s u holds, and u transitions to t via bpe_greedy_step_with (k + 2) u t.

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 k-step greedy BPE run with fresh symbol IDs 2, 3, ..., k + 1. -/
def bpe_greedy_run : ℕ → List ℕ → List ℕ → Prop
| 0, s, t => s = t
| k + 1, s, t => ∃ u, bpe_greedy_run k s u ∧ bpe_greedy_step_with (k + 2) u t
See it in the graphDiscuss this resultChallenge it