Concrete queue, visited-array, spill, and scan invariant for reverse search
DefinitionDirKECC1549_Main_ReverseSearchQueueInvariantThis defines the full assertion used at the fixed reverse-search program's queue-test counter 70. It is a predicate of a graph G, root r, original memory M, and current machine state s; it contains no assertion that executions satisfy the predicate.
Let B=n+2m+3. The state must be running at counter 70. Registers 1, 3, 4, and 5 hold n, m, B, and r, respectively. Registers 6, 7, and 8 hold the parent, visited, and queue bases
Register 2 holds the spill base S=16B+64. The spill words reproduce the original cells 0 through 16, and every original word at addresses strictly above 16 and below 6B is unchanged.
There are a parent map P, a discovery list L, and scanned-edge set E_s forming a ReverseScanTrace. The list has no repeated vertices and has length at most n. Registers 9 and 10 contain a processed-prefix length h and queue tail t satisfying
Every edge entering the processed prefix has been scanned, and the parent array encodes P. The physical queue and visited flags agree with L:
The predicate packages both the external certificate and the concrete register/array representation needed for initialization and preservation proofs. Those proofs are separate theorem obligations.
import Definitions.Def_DirKECC1549_Main_Machine
import Definitions.Def_DirKECC1549_Main_ReverseSearchCode
import Definitions.Def_DirKECC1549_Main_ReverseScanTrace
set_option autoImplicit false
open WordRAM
namespace DirKECC1549.Main
/-- Concrete queue-test invariant. The list contains every vertex ever enqueued;
the head indexes its processed prefix and the tail equals its length. -/
structure ReverseSearchQueueInvariant {n m : ℕ} {w : Width}
(G : Fin m → Fin n × Fin n) (r : Fin n) (initial : Memory w) (s : State w) : Prop where
pc_eq : s.pc = 70
running : s.halted = false
registers :
(s.mem 1).toNat = n ∧ (s.mem 3).toNat = m ∧ (s.mem 4).toNat = blk n m ∧
(s.mem 5).toNat = r ∧ (s.mem 6).toNat = 6 * blk n m ∧
(s.mem 7).toNat = 8 * blk n m + 64 ∧ (s.mem 8).toNat = 10 * blk n m + 64
spill_pointer : (s.mem 2).toNat = 16 * blk n m + 64
saved_zero : s.mem (16 * blk n m + 64 + 16) = initial 0
saved_registers : ∀ a : ℕ, 1 ≤ a → a ≤ 16 →
s.mem (16 * blk n m + 64 + a - 1) = initial a
input_frame : ∀ a : ℕ, 16 < a → a < 6 * blk n m → s.mem a = initial a
search : ∃ (par : Fin n → Fin n) (order : List (Fin n)) (scanned : Finset (Fin m)),
ReverseScanTrace G r par order scanned ∧ order.Nodup ∧ order.length ≤ n ∧
(s.mem 9).toNat ≤ order.length ∧ (s.mem 10).toNat = order.length ∧
(∀ e : Fin m, (G e).2 ∈ order.take (s.mem 9).toNat → e ∈ scanned) ∧
(∀ v : Fin n, (s.mem (arrayCell n m v)).toNat = par v) ∧
(∀ (i : ℕ) (hi : i < order.length),
(s.mem (10 * blk n m + 64 + i)).toNat = order[i]) ∧
(∀ v : Fin n, (s.mem (8 * blk n m + 64 + v)).toNat = if v ∈ order then 1 else 0)
end DirKECC1549.Main