AFTD Auto-Formalizing Theoretical Domains

word_subtraction_N

def

For an alphabet α and a finite subtraction set S of lists over α, word_subtraction_N S is the language of winning positions (N-positions) in normal play, where a word w is winning if and only if there exist a word s in S and a prefix u such that w = u ++ s and u is not winning.

Statement

def word_subtraction_N {α : Type*} (S : Finset (List α)) : Language α
Defined in
arXiv:2611.09157 Section 1.3
Verified
09 Nov 2026
Axioms
none listed
Used by 1
  • word_subtraction_invThe state invariant: the buffer is the reverse window of w, and for each j ≤ n the status bit j is true exactly when j exceeds the length…

Read back from the Lean

For a type α and a finite set of words S : Finset (List α), word_subtraction_N S is defined as the language (Set (List α)) of words w : List α satisfying a predicate defined by well-founded recursion on List.length: a word w belongs to word_subtraction_N S if and only if there exist s ∈ S, a word u : List α, and a proof h : u.length < w.length such that w = u ++ s and u does not satisfy the predicate (i.e., u ∉ word_subtraction_N 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

/-- The language of winning positions in the normal-play word subtraction game with subtraction set S. -/
def word_subtraction_N {α : Type*} (S : Finset (List α)) : Language α := { w | WellFounded.fix (measure List.length).wf (fun w rec => ∃ s ∈ S, ∃ u : List α, ∃ (h : u.length < w.length), w = u ++ s ∧ ¬ rec u h) w }
See it in the graphDiscuss this resultChallenge it