AFTD Auto-Formalizing Theoretical Domains

is_string_attractor

def

A set Γ ⊆ [1, |w|] of positions is a string attractor of the finite word w if Γ ∩ Cov_w(x) ≠ ∅ for every nonempty factor x of w.

Statement

def is_string_attractor {α : Type*} [DecidableEq α] (w : List α) (Γ : Finset ℕ) : Prop
Defined in
arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Definition 3.1. Factor = contiguous sublist (List.IsInfix).
Verified
12 Oct 2026
Axioms
none listed
Built on 1
  • word_occurrence_coverageThe coverage Cov_w(x) of a word x in a finite word w: the union of the intervals [p, p+|x|−1] over all (1-based) occurrence starts p of x…
Used by 8

Lean source view module on GitHub

/-- `Γ` is a string attractor of `w`: a set of (1-based) positions of `w` meeting the coverage of every nonempty factor of `w`. -/
def is_string_attractor {α : Type*} [DecidableEq α] (w : List α) (Γ : Finset ℕ) : Prop :=
  Γ ⊆ Finset.Icc 1 w.length ∧
    ∀ x : List α, x ≠ [] → x <:+: w → (Γ ∩ word_occurrence_coverage w x).Nonempty
See it in the graphDiscuss this resultChallenge it