Documentation

Complexitylib.Models.RandomAccessMachine.Simulation.RegisterStore.Machine.EntryCleanup

Sparse-entry miss cleanup #

This module exposes the exact invariant-restoring miss branch used by the bounded sparse register-store scan.

theorem Complexity.RAM.RegisterStore.Machine.entryMissCleanupTM_hoareTime_frame {n : } (tapes : EntryMatchTapes n) (entry : Entry) (rest queryBits : List Bool) (initialWork matchedWork : Fin nTape) (inp₀ out₀ : Tape) (hmatch : ReadableEntryMatch tapes entry rest queryBits initialWork matchedWork) (hinput : TM.Parked inp₀) (houtput : TM.Parked out₀) :
(entryMissCleanupTM tapes).HoareTime (fun (inp : Tape) (work : Fin nTape) (out : Tape) => inp = inp₀ work = matchedWork out = out₀) (fun (inp : Tape) (work : Fin nTape) (out : Tape) => inp = inp₀ EntryScanReady tapes rest queryBits initialWork work out = out₀) (entryMissCleanupTime tapes entry queryBits initialWork)

After a failed readable entry match, rewind the preserved query and reset all seven decoder/result scratch tapes, restoring the next-iteration frame.

Miss cleanup preserves one-way output safety.

theorem Complexity.RAM.RegisterStore.Machine.entryMissCleanupTM_prefix_withinAuxSpace {n : } (tapes : EntryMatchTapes n) (entry : Entry) (queryBits : List Bool) (initialWork : Fin nTape) (inputLength initialSpace time : ) (start current : Complexity.Cfg n (entryMissCleanupTM tapes).Q) (hinitial : start.WithinAuxSpace inputLength initialSpace) (hreach : (entryMissCleanupTM tapes).reachesIn time start current) (htime : time entryMissCleanupTime tapes entry queryBits initialWork) :
current.WithinAuxSpace inputLength (initialSpace + entryMissCleanupTime tapes entry queryBits initialWork)

Coarse all-prefix auxiliary-space envelope for miss cleanup.