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

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.

Read the Lean proof on GitHub

Description

The construction is the pair of explicit matrix graphs, with vertices listed in the order ordLIordL I produced by the compiler machine and colors the position of the first vertex of a class (Compiler.compileMCompiler.compileM): 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 (Compiler.reGraphspecCompiler.reGraph_spec). Colors and edge endpoints are numbers below 3∣V∣3 |V|, so the encoding has length O((S+1)log(S+2))O((S + 1) log (S + 2)) (Compiler.lengthoutlelogCompiler.length_out_le_log). The construction time is witnessed by the counter-machine program progp4Schprog p4Sch (Compiler/ProgCompiler/Prog): the passes P0P0–P3P3 compute the location and schema data and the answers of the join, P4P4 emits both graph descriptions, its schema edge part p4Schp4Sch meeting the interface SchSpecSchSpec with linear cost (p4Schspecp4Sch_spec); the program is compiled to a Turing machine running in time O((H+S)log3(H+S+2))O((H + S) log³ (H + S + 2)).