AFTD Auto-Formalizing Theoretical Domains

word_occurrence_coverage_ababa_aba

theoremverified

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.

  1. 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.

    line 3

      decide

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

theorem word_occurrence_coverage_ababa_aba :    word_occurrence_coverage [0, 1, 0, 1, 0] [0, 1, 0] = Finset.Icc 1 5 := by  decide
See it in the graphDiscuss this resultChallenge it