While this submission is a draft, it cannot be used by other submissions.

Proof of `Packed implicit parity systems for deterministic computations`

groundedproofs/Lax119563Proofs/Reduction/PackedMain.lean · lax-119563

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The system is IvMxsℓHIv M x s ℓ H (the compiled code-ordered verifier program), with ℓℓ the packed width and H=max(h,ℓ)≤h+1H = max(h, ℓ) ≤ h + 1; its correctness and the O((h+1)2)O((h + 1)^2) bounds on locations and schemas are packedboundshpacked_bounds_h. The machine is the composition of the preprocessor pkPrepkPre (pkPrecomputesWithinpkPre_computesWithin: it reads h,sh, s and writes the input as records of 1616 symbols carrying xkx_k and the flags [k<∣x∣],[k<h],[k<s][k < |x|], [k < h], [k < s], in time O((2ℓ+h)(h+1)2)O((2^ℓ + h) (h + 1)^2)) and the machine of the packed generator redGenPMredGenP M (redGenPcomputesWithinredGenP_computesWithin): a generator in the stack language GnGn whose loops over blocks and registers run up to runtime values, analysed with growth classes on two scales (2ℓ2^ℓ times a factor O(h)O(h) for the input length and the register values, and (h+3)2(h + 3)^2 for the linear quantities), in time O(2ℓ(h+1)37)O(2^ℓ (h + 1)^37).