AFTD Auto-Formalizing Theoretical Domains

pathGreedyRun_identity

theoremverified

The greedy matching count and pending run parity satisfy an exact counting identity.

Statement

open scoped BigOperators in
theorem pathGreedyRun_identity (p : Bool) (xs : List Bool) :
    2 * pathGreedyRun p xs + (if p then 1 else 0) = xs.countP id + pathOddRunFinish p xs
Source
Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
Verified
11 Nov 2026
Axioms
Quot.soundpropext
Built on 2
Used by 1

Lean source view module on GitHub

open scoped BigOperators in
theorem pathGreedyRun_identity (p : Bool) (xs : List Bool) :
    2 * pathGreedyRun p xs + (if p then 1 else 0) = xs.countP id + pathOddRunFinish p xs := by
  induction xs generalizing p with
  | nil => cases p <;> rfl
  | cons b bs ih =>
    cases p <;> cases b <;> simp [pathGreedyRun, pathOddRunFinish, List.countP_cons] at * <;> omega
See it in the graphDiscuss this resultChallenge it