The bottom-up computation of Theorem 1.16 on a word RAM in time
OpenCoDecompFO.fold_programFix a finite relational signature . This is the algorithmic half of Theorem 1.16: it asks for the program and its running time, and describes the output through the bottom-up computation instead of through the truth of the sentence.
There are one word-RAM program and one computable function such that, for every first-order -sentence with equality, every tree co-decomposition of -structures with bags and width at most , and every word width that holds the number , the program started on the code of halts within
steps, with the following output.
- If is non-empty, let be the number of quantifiers of and let be the matrix of its alternating form over with . For some root and some table of -hypotheticals on variables obtained at by the bottom-up computation over (the induced hypotheticals of the full strategy on the bags, then one reduced pullback and one projection per edge), prints if passes alternating evaluation of , and otherwise.
- If is empty, prints if and otherwise.
Together with the correctness of the bottom-up computation, this is Theorem 1.16. What is asked here is the implementation and its analysis: reading the code, ordering the tree from the leaves towards the root, representing the tables, whose number and size are bounded in and by Lemma 5.81, and computing pullbacks, projections and the final evaluation, with each node processed once.
Formalization Note The machine is the published word RAM with the multiplication instruction set, in the run layer LovaszECCKernel.RunsWithin, and the input is the code input φ T of CoDecompFO.theorem_1_16; the limit is not part of the input. The matrix is altMatrix φ with = quantCount φ, the bottom-up computation is CoDecomp.IsFold on T.withEq, and alternating evaluation is eval. The program may choose the root and the order in which the children of a node are joined. On an empty limit every universal quantifier holds and the alternating form is not equivalent to , so that case is stated directly on the limit.
import Mathlib import Definitions.Def_CoDecompFO_AltMatrix import Definitions.Def_CoDecompFO_Fold import Definitions.Def_LovaszECCKernel_RunsWithin import Definitions.Def_CoDecompFO_Codes set_option autoImplicit false
namespace CoDecompFO
open FirstOrder
/-- **The bottom-up computation in linear time** (Bumpus et al., *Co-Decompositions and FO Model
Checking*, arXiv:2611.04658, held file sha256 d550d7af…, proof of Theorem 1.16, p.41): "By Lemma 5.81, the
number and size of the reduced hypotheticals considered at any one node are bounded by a function of w and
|φ|. Since each node is processed once, the total running time is f_σ(w,|φ|)·b." Equality is handled on
`T°` (A.8, p.53: "lim(T°) = (lim(T))°"; A.9, p.53).
For each `σ` there are one word-RAM program `P` and one computable `f` such that on the code of `(φ, T)`,
on every word width that holds `f(w,|φ|)·b`, `P` halts within `f(w,|φ|)·b` steps and: if the limit is
non-empty, it prints the result of alternating evaluation of the matrix `altMatrix φ` on the table `H`
of some root `r`, for some bottom-up computation `T°.IsFold r (2ℓ) ℓ r univ H` over the co-decomposition
`T°` with equality, `ℓ = quantCount φ`; if the limit is empty, it prints whether `φ` holds in it.
**Formalization Note** This is the machine half of Theorem 1.16: its conclusion refers to the limit only
when the limit is empty, where every `∀` holds and the alternating form is not available. The program
may choose the root and the order in which children are joined. The machine and the code of the input
are those of `theorem_1_16`. -/
theorem fold_program (σ : Sig) :
∃ (P : LovaszECCKernel.Program) (f : ℕ → ℕ → ℕ), Computable₂ f ∧
∀ (T : CoDecomp σ) (φ : σ.lang.Sentence) (w : ℕ), width T ≤ w →
∀ W : WordRAM.Width, LovaszECCKernel.WordFits W (f w (sentLen φ) * T.b) →
(IsEmpty T.Lim →
(T.Lim ⊨ φ → LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [1]) ∧
(¬ T.Lim ⊨ φ → LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [0])) ∧
(Nonempty T.Lim →
∃ (r : Fin T.b)
(H : HTh (sigmaEq σ) (Fin (T.withEq.bag r).n) (2 * quantCount φ) (quantCount φ)),
T.withEq.IsFold r (2 * quantCount φ) (quantCount φ) r Set.univ H ∧
(eval (altMatrix φ) (quantCount φ) H →
LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [1]) ∧
(¬ eval (altMatrix φ) (quantCount φ) H →
LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [0])) := by sorry
end CoDecompFO