AFTD Auto-Formalizing Theoretical Domains

word_insertion_degree

def

The minimum insertion degree word_insertion_degree u v w of word w with respect to source words u and v is the infimum in WithTop Nat of mask_u_runs M over all binary masks M satisfying is_word_mask u v w M.

Statement

noncomputable def word_insertion_degree {α : Type*} (u v w : List α) : WithTop ℕ
Defined in
arXiv:2610.39941, Section 3
Verified
31 Oct 2026
Axioms
none listed
Built on 2
  • mask_u_runsThe number of maximal nonempty U-runs in a binary mask M is defined by mask_u_runs M = mask_u_runs_aux false M, counting contiguous blocks…
  • is_word_maskA binary mask of a word with respect to sources u and v has the same length as the word and projects to u on true and to v on false.

Read back from the Lean

For a type α and lists u, v, and w of elements of α, word_insertion_degree u v w is the infimum (in WithTop ℕ, i.e., ℕ ∪ {∞}) of the number of maximal contiguous runs of trues in M, taken over all boolean masks M : List Bool such that M is a valid interleaving mask of u and v to form w (that is, is_word_mask u v w M holds). If no such mask M exists, the set is empty and the value is ⊤ (infinity).

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

/-- Minimum insertion degree of w with respect to sources u, v, or top if w is not a shuffle. -/
noncomputable def word_insertion_degree {α : Type*} (u v w : List α) : WithTop ℕ :=
  sInf { (mask_u_runs M : WithTop ℕ) | (M : List Bool) (_ : is_word_mask u v w M) }
See it in the graphDiscuss this resultChallenge it