Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bottom-up dynamic programming over a tree co-decomposition on a word RAM in time f(w,∣φ∣)⋅bf(w,|\varphi|)\cdot bf(w,∣φ∣)⋅b

Open
CoDecompFO.tree_dp_program

by emmgaml · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

co-decompositionsmodel-checkingparameterized-complexityword-ram

Fix a finite relational signature σ\sigmaσ. 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 leaf\mathrm{leaf}leaf, join\mathrm{join}join, acc\mathrm{acc}acc be primitive recursive functions from lists of numbers to numbers, with acc≤1\mathrm{acc}\le1acc≤1, and let BBB be a computable function. Assume that for every first-order σ\sigmaσ-sentence φ\varphiφ and every tree co-decomposition T\mathcal TT of width at most www, every table vvv of a bottom-up computation with numeric tables on T\mathcal TT, with leaf\mathrm{leaf}leaf, join\mathrm{join}join and the parameter ⟨φ⟩\langle\varphi\rangle⟨φ⟩, satisfies v≤B(w,∣φ∣)v\le B(w,|\varphi|)v≤B(w,∣φ∣).

Then there are one word-RAM program PPP and one computable function fff such that for every φ\varphiφ, every T\mathcal TT with bbb bags and width at most www, and every word width that holds the number f(w,∣φ∣)⋅bf(w,|\varphi|)\cdot bf(w,∣φ∣)⋅b, the program PPP started on the code of (φ,T)(\varphi,\mathcal T)(φ,T) halts within

f(w,∣φ∣)⋅bf(w,|\varphi|)\cdot bf(w,∣φ∣)⋅b

steps and prints the single number acc(⟨φ⟩,v)\mathrm{acc}(\langle\varphi\rangle,v)acc(⟨φ⟩,v), where vvv is the root table of some bottom-up computation with leaf\mathrm{leaf}leaf and join\mathrm{join}join, for some root.

This is the step "since each node is processed once, the total running time is fσ(w,∣φ∣)⋅bf_\sigma(w,|\varphi|)\cdot bfσ​(w,∣φ∣)⋅b" 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.

Preamble
import Mathlib
import Definitions.Def_CoDecompFO_CodeFold
import Definitions.Def_LovaszECCKernel_RunsWithin
import Definitions.Def_CoDecompFO_Codes

set_option autoImplicit false
Formal statement
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
Source
Bumpus, Gomes, Larios-Jones, Turner, Co-Decompositions and FO Model Checking, arXiv:2611.04658 (held file sha256 d550d7af…), proof of Theorem 1.16, p.41

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me