Proof of `Far composition of type trees`
groundedproofs/Lax185574Proofs/FarComposition.lean · lax-185574
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
In the paper
- page 44 of this submission's paper
Description
The program runs a glue program and the three programs of the restriction lemma, the rank shift lemma and the canonical form observation in the loop driver. The glue program runs the recursion of the far composition with an explicit stack of frames: each round reads the stack and the answer to its last question, does one step of the recursion and asks the next question, a rank shift, a restriction or a canonical form, or writes the type tree of the concatenation. Before it halts, every round checks that the question is admissible for the program that answers it, that the round counter is small against the word length of its region, and that its output fits, so every halting run inside the driver is right.
The proof is carried out for the notion , and transferred to through .