AFTD Auto-Formalizing Theoretical Domains

word_subtraction_inv

def

The 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 of w or the prefix of w of length w.length - j is a winning position.

Statement

def word_subtraction_inv {α : Type*} (S : Finset (List α)) (n : ℕ) (w : List α)
    (st : (Fin n → Option α) × (Fin (n + 1) → Bool)) : Prop
Source
step towards word_subtraction_is_regular
Verified
09 Nov 2026
Axioms
none listed
Built on 2
  • word_subtraction_bufferThe buffer of a word w in a window of width n: the i-th letter of w from the right, or none if w has at most i letters.
  • word_subtraction_NFor an alphabet α and a finite subtraction set S of lists over α, word_subtraction_N S is the language of winning positions (N-positions)…

Lean source view module on GitHub

/-- Correctness invariant of the state relative to the word read so far. -/
def word_subtraction_inv {α : Type*} (S : Finset (List α)) (n : ℕ) (w : List α)
    (st : (Fin n → Option α) × (Fin (n + 1) → Bool)) : Prop := st.1 = word_subtraction_buffer n w ∧
    ∀ j : Fin (n + 1),
      (st.2 j = true ↔ ((j : ℕ) > w.length ∨ w.take (w.length - (j : ℕ)) ∈ word_subtraction_N S))
See it in the graphDiscuss this resultChallenge it