AFTD Auto-Formalizing Theoretical Domains

pathCertReachable

def

The 44 states reachable by the greedy matching automaton on four-color words.

Statement

open scoped BigOperators in
def pathCertReachable (a : Fin 4) (s : Fin 128) : Bool
Source
Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
Verified
11 Nov 2026
Axioms
none listed
Used by 3
  • pathCertStepEach reachable transition remains reachable and respects the path certificate potential.
  • pathCertRunBoundThe accumulated signed greedy count is bounded by the finite-state potential.
  • 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 pathCertReachable (a : Fin 4) (s : Fin 128) : Bool :=
  decide ((a.val = 0 ∧ s.val ∈ [0,1,9,17,25,33,41,45,49,51,89]) ∨
  (a.val = 1 ∧ s.val ∈ [0,2,10,18,26,30,34,42,50,51,106]) ∨
  (a.val = 2 ∧ s.val ∈ [0,4,12,20,28,30,36,44,45,52,116]) ∨
  (a.val = 3 ∧ s.val ∈ [0,64,72,80,88,89,96,104,106,112,116]))
See it in the graphDiscuss this resultChallenge it