The in-list and backtrack cases of a search step
ProvedDirKECC1549.Asm.dsElse_specWhen the out-block of the top vertex is exhausted, the step code either explores the next flipped in-edge of or pops , realizing the abstract DFS step and maintaining the representation.
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_L1Step3
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549.Main DirKECC1549.Main.CostAux
open DirKECC1549 DirKECC1549.Asm
variable {w : Width} {n m : ℕ}theorem DirKECC1549.Asm.dsElse_spec (E : Env) (mm orig : Memory w) (hm : 0 < m) (P : LP) (B : Fin m → Fin n × Fin n)
(perm : Equiv.Perm (Fin m)) (F : Finset (Fin m)) (Ep : ℕ) (v : Fin n) (st : DS n m)
(hC : LsC P orig mm B perm F) (hD : DRep hm P B perm F Ep v st mm)
(hI : DInv (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)) v st)
(hA : AdjOK (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)))
(x : Fin n) (hx : st.stk.getLast? = some x) (r1 : ℕ) (hr1 : (outL B perm x).length ≤ r1)
(hr1' : r1 ≤ (outL B perm x).length + (inL hm (fun x => its B x) P.CF P.IN mm x).length)
(hcur : st.cur x = curOf B perm F x r1)
(h2 : (mm 2).toNat = ots B x + r1) (h3 : (mm 3).toNat = ots B (x + 1)) (h10 : (mm 10).toNat = x) :
Run E dsElse mm (fun t mm' => t ≤ 70 ∧
DRep hm P B perm F Ep v (dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)) st) mm' ∧
(∀ a, (13 ≤ a ∧ a ≤ 25) ∨ a = 27 ∨ (28 ≤ a ∧ a < P.VIS) ∨ P.CF ≤ a → mm' a = mm a) ∧
(∀ z : Fin n, z ∈ st.stk → z ≠ x → mm' (P.RC + z) = mm (P.RC + z)) ∧
(x ∈ (dsStep (flipEdges B F) (adjOf B perm F (inL hm (fun x => its B x) P.CF P.IN mm)) st).stk →
(mm' (P.RC + x)).toNat = ots B x + r1 + 1)) := by sorry