pathOddRunFinish_identity
theoremverified
The pending parity counter agrees with the existing odd-run counter.
Statement
open scoped BigOperators in theorem pathOddRunFinish_identity (ir odd : Bool) (xs : List Bool) : odd_run_aux ir odd (xs ++ [false]) = pathOddRunFinish (ir && odd) xs
- Source
- Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
- Verified
- 11 Nov 2026
- Axioms
propext- Built on 2
- odd_run_aux
odd_run_aux inRun oddLen lscans the boolean listlleft to right, keeping a flaginRun(currently inside a run oftrues) and… - pathOddRunFinishCount odd true runs while retaining a pending run parity.
- odd_run_aux
- Used by 1
- pathGreedyRun_eq_count_and_oddTwice the greedy count equals the number of true edges plus the number of odd true runs.
Lean source view module on GitHub
open scoped BigOperators in theorem pathOddRunFinish_identity (ir odd : Bool) (xs : List Bool) : odd_run_aux ir odd (xs ++ [false]) = pathOddRunFinish (ir && odd) xs := by induction xs generalizing ir odd with | nil => cases ir <;> cases odd <;> rfl | cons b bs ih => cases ir <;> cases odd <;> cases b <;> simp [odd_run_aux, pathOddRunFinish, ih]