Proof of `Construction sequences with few realized types`
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 17 of this submission's paper
Description
The proof of the few-types theorem. Run the algorithm of the theorem on definable construction sequences with radius , where is the radius of the lemma passing from definability to few types. The output is radius- definable with predicates and parameters, so its radius- depth- width is at most , which is . So works for the width and the length, and since . The exponent of the time is passed on to the theorem on definable construction sequences. The program is a simulation of the program of the theorem on definable construction sequences on the rewritten input, one word bit shorter, and the word-length exponent grows by one to pay for the larger first entry.
The proof is carried out for the input format with the graph in compressed sparse row form and the notion . The algorithm converts the word of the graph into compressed sparse rows () and runs the program for that format. The script of a graph is the one whose encoding the program outputs on the converted input.