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
- is_string_attractor_IccThe set of all positions [1, |w|] is a string attractor of w.
- thue_morse_random_attractor_prob_zeroFor every natural number n, thue_morse_random_attractor_prob n 0 = 0.
- thue_morse_random_attractor_prob_mem_unit_intervalFor all n and k, 0 ≤ thue_morse_random_attractor_prob n k ≤ 1.
- is_string_attractor_iff_forall_min_factor_coverageFor every finite word w and every Γ ⊆ [1, |w|], Γ is a string attractor of w if and only if Γ ∩ C ≠ ∅ for every inclusion-minimal factor…
- not_is_string_attractor_emptyThe empty set is not a string attractor of a nonempty word.
- fibonacci_string_attractor_iff_meets_basisFor any natural number n, assuming the inclusion-minimal factor coverages of F_n are exactly the coverages of the basis B_n…
- word_min_factor_coverages_subset_of_certificateLet F ⊆ H(w) be a family of factor coverages such that for every Γ ⊆ [1, |w|], Γ is a string attractor of w iff Γ meets every member of F.…
- thue_morse_random_attractor_probFor natural numbers n and k, the real number defined as the ratio whose numerator is the cardinality of the finset of functions f : Fin k…
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