AFTD Auto-Formalizing Theoretical Domains

pathCertTake

def

Greedy matching choice for one cut when a path edge is appended.

Statement

open scoped BigOperators in
def pathCertTake (a b : Fin 4) (s : Fin 128) (j : Fin 7) : Bool
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
  • pathCertMaskThe seven party-union masks for a four-color path word.
Used by 4
  • pathCertDeltaThe signed change of the seven greedy matching counts for one appended vertex.
  • 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.
  • pathCertNextThe seven greedy-matching flags after appending a colored vertex.

Lean source view module on GitHub

open scoped BigOperators in
def pathCertTake (a b : Fin 4) (s : Fin 128) (j : Fin 7) : Bool :=
  (Nat.testBit (pathCertMask j) a.val != Nat.testBit (pathCertMask j) b.val) &&
    !(Nat.testBit s.val j.val)
See it in the graphDiscuss this resultChallenge it