Six root-marking and enqueue instructions establish the queue invariant
ProvedDirKECC1549.Main.reverse_search_root_setup_blockLet G have n vertices and m edges with root r, and let B=n+2m+3. Let s be any state satisfying ReverseSearchRootSetupPre for these sizes, root, and original memory M. Under the word-width bound 32B+256 at most 2^w, running the actual reverseSearchAlgorithm for six instructions from s gives a state satisfying
The prepared state starts running at counter 64, with fixed scalar registers and saved input words, identity parents, and zero visited flags. No queue contents or head/tail values are assumed. The conclusion includes running counter 70, preserved scalar/spill/frame data, a valid parent array and abstract scan trace, and agreement of the physical queue and visited flags with the discovery order.
This theorem verifies the specific instruction block at counters 64–69 independently of how the prepared state was reached. No graph-layout premise is needed beyond the explicit prepared-state assertion; the graph is used to instantiate the initial abstract trace.
import Definitions.Def_DirKECC1549_Main_ReverseSearchQueueInvariant import Definitions.Def_DirKECC1549_Main_ReverseSearchRootSetupPre set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_root_setup_block (n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (initial : Memory w) (s : State w)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hpre : ReverseSearchRootSetupPre n m r initial s) :
ReverseSearchQueueInvariant G r initial
(run Uniform.noConstants (Complexity.Program.lower w reverseSearchAlgorithm.code) 6 s) := by sorry
end DirKECC1549.Main