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))