Bottom-up dynamic programming over a tree co-decomposition on a word RAM in time
OpenCoDecompFO.tree_dp_programFix a finite relational signature . This statement is about the machine only: a word RAM can run a bottom-up computation over a tree co-decomposition, given by its code with the tree as an edge list, in time linear in the number of bags, when the local operations are primitive recursive and the tables are bounded.
Let , , be primitive recursive functions from lists of numbers to numbers, with , and let be a computable function. Assume that for every first-order -sentence and every tree co-decomposition of width at most , every table of a bottom-up computation with numeric tables on , with , and the parameter , satisfies .
Then there are one word-RAM program and one computable function such that for every , every with bags and width at most , and every word width that holds the number , the program started on the code of halts within
steps and prints the single number , where is the root table of some bottom-up computation with and , for some root.
This is the step "since each node is processed once, the total running time is " of the proof of Theorem 1.16, for arbitrary local operations. It involves reading the code of the input, finding an order from the leaves towards the root in a tree given as an edge list, and evaluating primitive recursive functions on bounded arguments at unit cost per instruction.
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 numeric computation is CoDecomp.CodeFold, with arguments passed as one list, each preceded by its length (frame). The program may choose the root and the order in which the children of a node are joined.
import Mathlib import Definitions.Def_CoDecompFO_CodeFold import Definitions.Def_LovaszECCKernel_RunsWithin import Definitions.Def_CoDecompFO_Codes set_option autoImplicit false
namespace CoDecompFO
open FirstOrder
/-- **Bottom-up dynamic programming on a word RAM in time linear in the number of bags** (Bumpus et al.,
*Co-Decompositions and FO Model Checking*, arXiv:2611.04658, held file sha256 d550d7af…, proof of
Theorem 1.16, p.41: "process the co-decomposition from the leaves towards the root … Since each node is
processed once, the total running time is f_σ(w,|φ|)·b").
Let `leaf`, `join`, `acc` be primitive recursive functions on lists of numbers, with `acc ≤ 1`, and let
`B` be a computable function such that every table of a bottom-up computation with `leaf` and `join`, on
the code of a sentence `φ` and a co-decomposition of width at most `w`, is at most `B(w,|φ|)`. Then 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 prints `acc` of the code of `φ` and the
root table `v` of some bottom-up computation, for some root.
**Formalization Note** No logic occurs: the statement is about reading the code of the input, ordering
the tree given as an edge list, and running three primitive recursive functions whose values are bounded.
The machine and the code of the input are those of `theorem_1_16`. The program may choose the root and
the order in which children are joined. -/
theorem tree_dp_program (σ : Sig) (leaf join acc : List ℕ → ℕ)
(hleaf : Primrec leaf) (hjoin : Primrec join) (hacc : Primrec acc) (hacc1 : ∀ l, acc l ≤ 1)
(B : ℕ → ℕ → ℕ) (hB : Computable₂ B)
(hbound : ∀ (T : CoDecomp σ) (φ : σ.lang.Sentence) (w : ℕ), width T ≤ w →
∀ (r t : Fin T.b) (S : Set (Fin T.b)) (v : ℕ),
T.CodeFold r (encF φ) leaf join t S v → v ≤ B w (sentLen φ)) :
∃ (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) →
∃ (r : Fin T.b) (v : ℕ), T.CodeFold r (encF φ) leaf join r Set.univ v ∧
LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b)
[acc (frame [encF φ, [v] ])] := by sorry
end CoDecompFO