Verified initialization of all parent and visited entries in 7n+1 instructions
ProvedDirKECC1549.Main.reverse_search_initialize_arraysLet B=n+2m+3 and let r be a vertex among n vertices. Suppose a state s satisfies ReverseSearchArrayInitPre with respect to original memory M: it is running at counter 57, its scalar/spill data are prepared, and register 11 contains zero. The parent and visited arrays may be arbitrary. Under the word-width bound 32B+256 at most 2^w,
holds for the actual lowered reverseSearchAlgorithm.
In particular, execution reaches running counter 64 with identity parent entries and every visited flag zero. Scalar registers, saved original input words, and the protected input region are preserved. No graph-edge information or prior contents of the initialized arrays is assumed.
This theorem verifies the complete loop at counters 57–63, including all n iterations and its final exit test. It does not mark or enqueue the root; the following six instructions handle that separate stage.
import Definitions.Def_DirKECC1549_Main_ReverseSearchArrayInitPre set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_initialize_arrays (n m : ℕ) (r : Fin n) (w : Width) (initial : Memory w) (s : State w)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hpre : ReverseSearchArrayInitPre n m r initial s) :
ReverseSearchRootSetupPre n m r initial
(run Uniform.noConstants (Complexity.Program.lower w reverseSearchAlgorithm.code)
(7 * n + 1) s) := by sorry
end DirKECC1549.Main