word_occurrence_coverage_ababa_aba
The 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 as 0, 1).
Statement
theorem word_occurrence_coverage_ababa_aba :
word_occurrence_coverage [0, 1, 0, 1, 0] [0, 1, 0] = Finset.Icc 1 5- Source
- Sanity lemma for word_occurrence_coverage: the example after Definition 3.1 of arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words).
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- 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…
The proof, explained
The theorem verifies the paper's running example: in the word $w = ababa$ (encoded as $[0, 1, 0, 1, 0]$), the factor $aba$ (encoded as $[0, 1, 0]$) occurs at positions 1 and 3, yielding coverage $[1, 3] \cup [3, 5] = [1, 5]$. Since all inputs are concrete finite lists and all operations on finite sets are decidable, the equality is proved by direct computation.
The coverage of the pattern `[0, 1, 0]` in the word `[0, 1, 0, 1, 0]` equals the integer interval `[1, 5]`. automation
Because both words are explicit finite lists, their occurrence positions (indices 1 and 3) and the resulting union of intervals $[1, 3] \cup [3, 5] = [1, 5]$ are completely computable. The `decide` tactic evaluates the finite set operations and confirms the equality algorithmically.
decide
- The proof relies entirely on computational reflection (`decide`), evaluating finite set operations directly on concrete lists.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem word_occurrence_coverage_ababa_aba : word_occurrence_coverage [0, 1, 0, 1, 0] [0, 1, 0] = Finset.Icc 1 5 := by decide