Grouping: processing one vertex
ProvedDirKECC1549.Asm.gBody_specOne iteration of the grouping loop reads the label of , computes its home cell, looks up or creates its group and stores it, establishing the invariant and state for within 60 ticks.
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
import Definitions.Def_DirKECC1549_Impl_L1Grp
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549 DirKECC1549.Asm
variable {w : Width}theorem DirKECC1549.Asm.gBody_spec (E : Env) (mm0 q : Memory w) (N LABb T GIb KEYb HOMEb ALTb FRTb : ℕ) (lab : ℕ → ℕ)
(hlay : GLay N LABb T GIb KEYb HOMEb ALTb FRTb w.bits) (hlab : ∀ y < N, (mm0 (LABb + y)).toNat = lab y)
(hlT : ∀ y < N, lab y < 2 ^ w.bits)
(x cnt : ℕ) (key alt gi hd : ℕ → ℕ) (hI : GInv T N lab x cnt key alt gi hd) (hx : x < N)
(hS : GSt mm0 q N LABb T GIb KEYb HOMEb ALTb FRTb x cnt key alt gi hd) :
Run E gBody q (fun t q' => ∃ (cnt' : ℕ) (key' alt' gi' hd' : ℕ → ℕ), GInv T N lab (x + 1) cnt' key' alt' gi' hd' ∧
GSt mm0 q' N LABb T GIb KEYb HOMEb ALTb FRTb (x + 1) cnt' key' alt' gi' hd' ∧ t ≤ 60) := by sorry