AFTD Auto-Formalizing Theoretical Domains

pathCertNext

def

The seven greedy-matching flags after appending a colored vertex.

Statement

open scoped BigOperators in
def pathCertNext (a b : Fin 4) (s : Fin 128) : 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 1
  • pathCertTakeGreedy matching choice for one cut when a path edge is appended.
Used by 5
  • pathCertNext_bitEach bit of the automaton state records the corresponding greedy matching choice.
  • pathCertRun_eq_greedyThe automaton output equals the signed sum of seven greedy edge counts.
  • pathCertStepEach reachable transition remains reachable and respects the path certificate potential.
  • pathCertRunBoundThe accumulated signed greedy count is bounded by the finite-state potential.
  • pathCertRunRun the seven simultaneous greedy matching counters on a colored path suffix.

Lean source view module on GitHub

open scoped BigOperators in
def pathCertNext (a b : Fin 4) (s : Fin 128) : Fin 128 :=
  ⟨(∑ j : Fin 7, if pathCertTake a b s j then 2 ^ j.val else 0) % 128, Nat.mod_lt _ (by decide)⟩
See it in the graphDiscuss this resultChallenge it