Observation A.8 —
ProvedCoDecompFO.observation_A_8co-decompositionsfirst-order-logicmodel-checkingp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexity
Let be a tree co-decomposition. Then
The two structures have the same matching families, and on the limit of , which holds coordinatewise in every bag, is equality of matching families.
This is why a program may evaluate equality by a linear pre-processing of the bags, instead of constructing the limit.
Differences from the source:
- encoding: the equality of structures lim(T°) = (lim T)° → an isomorphism that keeps every coordinate of a matching family; reason: the two point sets are different Lean types that have the same coordinates
Preamble
import Mathlib import Definitions.Def_CoDecompFO_Lim set_option autoImplicit false
Formal statement
namespace CoDecompFO
open FirstOrder
/-- **Observation A.8** (Bumpus et al., arXiv:2611.04658, held file sha256 d550d7af…, p.53): "Let T be
a co-decomposition. Then lim(T°) = (lim(T))°."
**Formalization Note** The equality is the isomorphism that keeps every coordinate of a matching
family. The content is that `∘` on the limit is equality of matching families. -/
theorem observation_A_8 {σ : Sig} (T : CoDecomp σ) :
∃ u : T.withEq.Lim ≃[(sigmaEq σ).lang] Circ σ T.Lim,
∀ (x : T.withEq.Lim) (t : Fin T.b),
CoDecomp.Lim.val (T := T) (u x) t = x.val t := by sorry
end CoDecompFO
Source
Bumpus, Gomes, Larios-Jones, Turner, Co-Decompositions and FO Model Checking, arXiv:2611.04658 (held file sha256 d550d7af…), Observation A.8, p.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.