AFTD Auto-Formalizing Theoretical Domains

is_word_run

deforiginal

A pair of indices 0 ≤ a < b ≤ n forms a run [a, b) of a word y : Fin n → α if all symbols y i for a ≤ i < b are equal, and the block cannot be extended to the left (a = 0 or y(a - 1) ≠ y a) or to the right (b = n or y b ≠ y a).

Statement

def is_word_run {n : ℕ} {α : Type*} (y : Fin n → α) (a b : ℕ) : Prop
Related work
folklore
Verified
11 Nov 2026
Axioms
none listed
Used by 5
  • is_longest_word_run_of_constantFor any constant word y on Fin n with 1 ≤ n, the interval [0, n) is a longest run of y.
  • op_1537_binary_length_two_one_deletionFor any nonconstant binary word y : Fin 2 → Fin 2 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run [a',…
  • is_word_run_of_constantFor any constant word y on Fin n with 1 ≤ n, the full interval [0, n) is a run of y.
  • op_1537_ternary_length_two_one_deletionFor any nonconstant ternary word y : Fin 2 → Fin 3 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run…
  • is_longest_word_runA run [a, b) of a word y : Fin n → α is a longest run if its length b - a is greater than or equal to the length b' - a' of every run [a',…

Read back from the Lean

Given a sequence y : Fin n → α of length n over a type α, and natural numbers a and b, is_word_run y a b asserts that a < b and b ≤ n, and the following three conditions hold: 1. For every index i : Fin n such that a ≤ i.val and i.val < b, y i is equal to y ⟨a, _⟩ (i.e., all symbols in y between indices a (inclusive) and b (exclusive) are identical to the symbol at index a). 2. Either a = 0, or there exists ha : 0 < a such that y ⟨a - 1, _⟩ ≠ y ⟨a, _⟩ (i.e., the run cannot be extended to the left). 3. Either b = n, or there exists hb : b < n such that y ⟨b, _⟩ ≠ y ⟨a, _⟩ (i.e., the run cannot be extended to the right).

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 contiguous block [a, b) of indices is a run of word y : Fin n → α if all letters in [a, b) are equal and it cannot be extended to the left or right. -/
def is_word_run {n : ℕ} {α : Type*} (y : Fin n → α) (a b : ℕ) : Prop := ∃ (hab : a < b) (hbn : b ≤ n),
    (∀ (i : Fin n), a ≤ i.val ∧ i.val < b → y i = y ⟨a, hab.trans_le hbn⟩) ∧
    (a = 0 ∨ ∃ (ha : 0 < a), y ⟨a - 1, by omega⟩ ≠ y ⟨a, hab.trans_le hbn⟩) ∧
    (b = n ∨ ∃ (hb : b < n), y ⟨b, hb⟩ ≠ y ⟨a, hab.trans_le hbn⟩)
See it in the graphDiscuss this resultChallenge it