A bottom-up computation with numeric tables on a rooted tree co-decomposition
DefinitionCoDecompFO_CodeFoldLet be a tree co-decomposition of -structures with bags , adhesions and maps , rooted at . Let be a list of numbers (a parameter, in the application the code of a sentence) and let and be functions from lists of numbers to numbers. The relation says that the number is the table held at the node once the set of nodes has been absorbed. It is generated by two rules.
- Base. , where is the code of the bag.
- Step. Let be an edge from to a child of with . If and , then
where and are the lists of values of the two maps into the adhesion.
The arguments of and are passed as a single list in which each argument is preceded by its length (frame). The table of the root is any with .
This is the bottom-up traversal of the proof of Theorem 1.16 with the tables and the operations on them left abstract. It separates two tasks: representing the tables of hypotheticals by numbers with computable operations, and running a bottom-up computation over a tree given as an edge list in time linear in the number of bags.
Formalization Note The relation has the shape of CoDecomp.IsFold, with numbers in place of hypotheticals. The codes of bags are those of encBag. The children of a node may be joined in any order.
import Mathlib
import Definitions.Def_CoDecompFO_Lim
import Definitions.Def_CoDecompFO_Codes
set_option autoImplicit false
namespace CoDecompFO
open FirstOrder
variable {σ : Sig}
/-- Several lists as one: each list preceded by its length. -/
def frame (ls : List (List ℕ)) : List ℕ := ls.flatMap (fun l => l.length :: l)
/-- **A bottom-up computation with numeric tables** on the tree of a co-decomposition rooted at `r`
(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, maintaining
at each node the reduced supported hypotheticals … Since each node is processed once, the total running
time is f_σ(w,|φ|)·b").
`T.CodeFold r p leaf join t S v` says that the number `v` is the table held at the node `t` after the
nodes of `S` have been absorbed, when a node alone gets the value of `leaf` on the parameter `p` and the
code of its bag (`base`), and absorbing the whole subtree of a child `c` along the edge `e` applies
`join` to the parameter, the codes of the bags of `t` and `c` and of the adhesion of `e`, the value lists
of the maps `g^e_t` and `g^e_c`, and the two tables (`step`). The arguments are passed as one list, each
preceded by its length (`frame`).
**Formalization Note** This is the shape of `CoDecomp.IsFold` with the hypotheticals replaced by numbers
and the operations by functions on codes, so that the tree traversal can be separated from the
operations. The children of a node may be joined in any order. -/
inductive CoDecomp.CodeFold (T : CoDecomp σ) (r : Fin T.b) (p : List ℕ) (leaf join : List ℕ → ℕ) :
Fin T.b → Set (Fin T.b) → ℕ → Prop
| base (t : Fin T.b) :
CoDecomp.CodeFold T r p leaf join t {t} (leaf (frame [p, encBag (T.bag t)]))
| step (t : Fin T.b) (S : Set (Fin T.b)) (e : Fin T.m) (he : T.IsChildEdge r t e) (v vc : ℕ) :
CoDecomp.CodeFold T r p leaf join t S v → T.child e t ∉ S →
CoDecomp.CodeFold T r p leaf join (T.child e t) (T.subtree r (T.child e t)) vc →
CoDecomp.CodeFold T r p leaf join t (S ∪ T.subtree r (T.child e t))
(join (frame [p, encBag (T.bag t), encBag (T.bag (T.child e t)), encBag (T.adh e),
List.ofFn (fun x => (T.edgeMap e t he.top_mem x).val),
List.ofFn (fun x => (T.edgeMap e (T.child e t) he.child_mem x).val), [v], [vc] ]))
end CoDecompFO