One first return to the queue test preserves the concrete invariant
OpenDirKECC1549.Main.reverse_search_queue_first_returnFix a graph G with n vertices and m edges, root r, original graph-layout memory M with encoded root, and word width satisfying 32B+256 at most 2^w, where B=n+2m+3. Let s be any state satisfying ReverseSearchQueueInvariant for G, r, and M.
Run the actual lowered reverseSearchAlgorithm from s, retaining its memory and tick count. Suppose positive interpreter fuel f gives a running state t at counter 70, and no intermediate fuel j with 0<j<f gives a running state at counter 70. Then
This is preservation across one complete first return of the queue loop. The starting state need not be assumed reachable from M beyond satisfying the explicit concrete invariant. The statement neither assumes preservation across multiple queue iterations nor asserts that a return exists or gives a tick bound. All register, spill, queue, visited-array, parent-array, and scan-history conditions are explicit in the imported invariant definition.
import Definitions.Def_DirKECC1549_Main_ReverseSearchQueueInvariant set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_queue_first_return
(n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (initial : Memory w) (s : State w) (fuel : ℕ)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hgraph : GraphLayout G initial)
(hroot : (initial (paramCell n m 2)).toNat = r)
(hinv : ReverseSearchQueueInvariant G r initial s)
(hpositive : 0 < fuel)
(hpc : (run Uniform.noConstants
(Complexity.Program.lower w reverseSearchAlgorithm.code) fuel s).pc = 70)
(hrunning : (run Uniform.noConstants
(Complexity.Program.lower w reverseSearchAlgorithm.code) fuel s).halted = false)
(hfirst : ∀ j : ℕ, 0 < j → j < fuel →
¬ ((run Uniform.noConstants
(Complexity.Program.lower w reverseSearchAlgorithm.code) j s).pc = 70 ∧
(run Uniform.noConstants
(Complexity.Program.lower w reverseSearchAlgorithm.code) j s).halted = false)) :
ReverseSearchQueueInvariant G r initial
(run Uniform.noConstants (Complexity.Program.lower w reverseSearchAlgorithm.code) fuel s) := by sorry
end DirKECC1549.Main