AFTD Auto-Formalizing Theoretical Domains

pathCertRun

def

Run the seven simultaneous greedy matching counters on a colored path suffix.

Statement

open scoped BigOperators in
def pathCertRun (a : Fin 4) (s : Fin 128) : List (Fin 4) → Fin 4 × Fin 128 × ℤ
Source
Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
Verified
11 Nov 2026
Axioms
none listed
Built on 2
  • pathCertNextThe seven greedy-matching flags after appending a colored vertex.
  • pathCertDeltaThe signed change of the seven greedy matching counts for one appended vertex.
Used by 4
  • pathCertRun_eq_greedyThe automaton output equals the signed sum of seven greedy edge counts.
  • pathCertRunBoundThe accumulated signed greedy count is bounded by the finite-state potential.
  • pathCertOddRunIneqFor any four-color path word, the signed sum of odd crossing-run counts for the seven masks is nonpositive.
  • pure_path_automaton_nonpositiveFor every four-color word, the signed sum of seven greedy path-edge matching counts is nonpositive.

Lean source view module on GitHub

open scoped BigOperators in
def pathCertRun (a : Fin 4) (s : Fin 128) : List (Fin 4) → Fin 4 × Fin 128 × ℤ
  | [] => (a,s,0)
  | b :: bs =>
    let (last, bits, val) := pathCertRun b (pathCertNext a b s) bs
    (last, bits, pathCertDelta a b s + val)
See it in the graphDiscuss this resultChallenge it