word_occurrence_coverage
def
The 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 in w, i.e. all p with w[p..p+|x|−1] = x.
Statement
def word_occurrence_coverage {α : Type*} [DecidableEq α] (w x : List α) : Finset ℕ
- Defined in
- arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Sec. 3.1, equation (1). Positions are 1-based as in the paper.
- Verified
- 12 Oct 2026
- Axioms
- none listed
- Used by 13
- is_string_attractor_IccThe set of all positions [1, |w|] is a string attractor of w.
- thue_morse_unhit_mean_nonnegFor all n and k, 0 ≤ thue_morse_unhit_mean n k.
- word_occurrence_coverage_subsetEvery coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
- fibonacci_attractor_basis_seven_coverage_distinctThe cardinality of the image under word_occurrence_coverage (fibonacci_word 7) of fibonacci_attractor_basis 7 is 7, showing that all 7…
- word_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors x of w.
- 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.…
- is_string_attractorA 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.
- word_occurrence_coverage_ababa_abaThe paper's example: in w = ababa the factor aba occurs at positions 1 and 3, so Cov_w(aba) = [1,3] ∪ [3,5] = [1,5] (letters a, b encoded…
- thue_morse_min_factor_coverages_finset_memFor every n and every C, C belongs to thue_morse_min_factor_coverages_finset n if and only if C is an inclusion-minimal factor coverage of…
- word_occurrence_coverage_nonemptyThe coverage of a nonempty factor of w is nonempty.
Lean source view module on GitHub
/-- Coverage of `x` in `w`: the union of the (1-based) intervals `[p, p+|x|-1]` over all starts `p` of occurrences of `x` in `w`. -/ def word_occurrence_coverage {α : Type*} [DecidableEq α] (w x : List α) : Finset ℕ := ((Finset.Icc 1 w.length).filter (fun p => (w.drop (p - 1)).take x.length = x)).biUnion (fun p => Finset.Icc p (p + x.length - 1))