Proof of `The matrix compiler`
groundedproofs/Lax119563Proofs/Matrix/Main.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.
Description
The construction is the pair of explicit matrix graphs, with vertices listed in the order produced by the compiler machine and colors the position of the first vertex of a class (): Spoiler follows a derivation of the conflict backwards through the strips with row sweeps, Duplicator maintains seed descriptions with coefficient bits repaired in an untouched repetition, the size bound counts the vertex list and the edge bound uses that every edge contains a hub of degree at most three (). Colors and edge endpoints are numbers below , so the encoding has length (). The construction time is witnessed by the counter-machine program (): the passes – compute the location and schema data and the answers of the join, emits both graph descriptions, its schema edge part meeting the interface with linear cost (); the program is compiled to a Turing machine running in time .