Multiteam Semantics

Origin. Arnaud Durand, Miika Hannula, Juha Kontinen, Arne Meier and Jonni Virtema, "Approximation and dependence via multiteam semantics" (FoIKS 2016, pp. 271–291; journal version Annals of Mathematics and Artificial Intelligence 83, 2018, pp. 297–320), which defined lax and strict multiteam semantics and the probabilistic inclusion and independence atoms, and the same five authors' "Probabilistic team semantics" (FoIKS 2018, Lecture Notes in Computer Science 10833, pp. 186–206), which replaced multisets by distributions. Teams with measure predate the names: Tapani Hyttinen, Gianluca Paolini and Jouko Väänänen, "Quantum team logic and Bell's inequalities" (Review of Symbolic Logic 8, 2015, pp. 722–742) reasoned about probabilities of first-order formulas in measure teams, and probabilistic variants of dependence and IF logic had been studied by Galliani, Mann, Sevenster and Sandu. Erich Grädel and Richard Wilke, "Logics with multiteam semantics" (ACM Transactions on Computational Logic 23(2), 2022) is the systematic development on the multiset side.

Models. A team is a set of assignments; a multiteam gives each assignment a multiplicity, and a probabilistic team gives it a weight, the weights summing to one. The generalization restores what the set discarded: an actual database table has duplicate rows, and a poll, a measurement record or a voting sample carries its information in frequencies, not in support. The Independence Logic entry closes on the fact that its atom has the probabilistic shape and no measure; multiteam semantics supplies the measure, and the transfer that entry warns against becomes a theorem — over a multiteam, the probabilistic conditional independence atom holds exactly when the induced distribution satisfies statistical conditional independence, Pr(ȳ, z̄ | x̄) = Pr(ȳ | x̄) · Pr(z̄ | x̄) (Durand, Hannula, Kontinen, Meier and Virtema 2018). The classical atoms survive unchanged on the support, so the two readings of a table — which rows occur, and how often — coexist in one framework.

Formalism.

Multiteam: a multiset of assignments 𝒳 = (X, m), with m: X → ℕ the multiplicity function. Literals: checked on the support — every s with m(s) ≥ 1 satisfies them. ∧: both conjuncts on the whole multiteam. ∨: the multiteam splits — 𝒴 ⊎ 𝒵 = 𝒳 (strict), covering submultisets (lax). ∀x: every row duplicated across the domain, multiplicities multiplying. ∃x: a function gives each row occurrence a nonempty multiset of witnesses.

Probabilistic team: a distribution 𝕏: X → ℚ ∩ [0,1] with Σ 𝕏(s) = 1, over a finite team X. Weight of a condition: |𝕏_x̄=ā| := Σ { 𝕏(s) : s(x̄) = ā }. Literals: on the support — every s with 𝕏(s) > 0 satisfies them. ∨: 𝕏 = k·𝕐 + (1−k)·𝕐′ for some k ∈ [0,1] with 𝕐 ⊨ φ and 𝕐′ ⊨ ψ — the split is a convex combination. ∀x: 𝕏[A/x] — each row's weight divided evenly over the domain, 𝕏(s) · 1/|A| per value. ∃x: 𝕏[F/x] — F gives each row a distribution over the domain; the row's weight is reapportioned by it.

Marginal identity: x̄ ≈ ȳ (tuples of equal length) iff |𝕏_x̄=ā| = |𝕏_ȳ=ā| for every ā — the values of x̄ and of ȳ are identically distributed. With ≤ for = this is the probabilistic inclusion atom of the 2016 paper; over distributions the two definitions coincide, so "probabilistic inclusion" and "marginal identity" name one atom.

Probabilistic conditional independence: ȳ ⫫_x̄ z̄ iff for every assignment s: |𝕏_x̄ȳ=s(x̄ȳ)| · |𝕏_x̄z̄=s(x̄z̄)| = |𝕏_x̄ȳz̄=s(x̄ȳz̄)| · |𝕏_x̄=s(x̄)|. The factorization of the induced distribution. ȳ ⫫_x̄ ȳ is the dependence atom =(x̄, ȳ).

Classical atoms over multiteams: =(x̄, ȳ), ⊆ and ⊥ are evaluated on the supporting team; multiplicities are invisible to them. ⫫ implies ⊥ and not conversely.

Symbols.

Metatheory. When every multiplicity is one, multiteam satisfaction coincides with team satisfaction, so the semantics is conservative over the sibling logics, and locality holds for the multiteam atoms. The statistical reading is exact in both directions: ⫫ on multiteams is statistical conditional independence of the induced distribution, and for pairwise disjoint tuples it is Wong's generalised embedded multivalued dependency of bag relational models (Durand et al. 2018). The expressivity yardstick shifts from Fagin's theorem to arithmetic. On the multiset side, Grädel and Wilke (2022) characterized multiteam inclusion–exclusion logic by the Presburger fragment of their existential second-order framework — addition on multiplicities suffices — while the independence atom requires multiplication. On the probabilistic side, the FoIKS 2018 paper related FO(⫫, ≈) to a two-sorted existential second-order logic with quantification over rational distributions, and Hannula, Kontinen, Van den Bussche and Virtema, "Descriptive complexity of real computation and probabilistic independence logic" (LICS 2020, pp. 550–563), fixed the independence atom's place: FO(⫫) is equivalent to the loose fragment L-ESO_[0,1][+, ×, ≤, 0, 1] — negated numerical atoms disallowed — and to NP on separate-branching BSS machines without real constants, which on Boolean inputs characterizes a fragment of ∃ℝ and so lies between NP and PSPACE. For the marginal identity atom, Hannula and Virtema, "Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals" (Annals of Pure and Applied Logic 173, 2022): probabilistic inclusion logic is captured by a fragment of additive real arithmetic, has PTIME data complexity by reduction to linear programming, and its atoms admit a sound and complete axiomatization. Hyttinen, Paolini and Väänänen gave complete axiomatizations for their quantum team and measure team logics. The classical atoms, being support-level, keep the Σ¹₁ sentence-level theory the Dependence Logic and Independence Logic entries record; the probabilistic atoms are the ones that leave Σ¹₁ for the reals.

Applies to. Database theory over bags, where multiset relations are the actual tables and the atoms are their dependencies. Statistics and graphical models: conditional independence reasoning with the measure present. Quantum information: Bell's inequalities and contextuality through probabilistic teams. Causal inference: causal multiteams carry Pearl-style interventionist counterfactuals with probabilities (Barbero, Sandu, Virtema). Approximate dependence — functional dependencies holding up to error, the 2016 paper's motivating operators.

Limitations. The classical atoms cannot see multiplicities, and the quantitative atoms answer only quantitative questions: key constraints, expressible by functional dependencies under team semantics, are not expressible under multiteam semantics (Durand et al. 2018). Lifting breaks the family's tractability landmarks — over multiteams, model checking is NP-hard already for very simple quantifier-free formulas with ≈ (FoIKS 2018), where the Galliani–Hella theorem keeps classical inclusion logic in PTIME — and the data-complexity ceiling for the independence atom is tied to ∃ℝ, whose exact strength between NP and PSPACE is a major open question. Axiomatization is atomic so far: marginal identity atoms have a complete axiomatization, but the implication problem for probabilistic conditional independence atoms is not finitely axiomatizable, and for the team atoms it is undecidable (both reported in the 2018 journal paper); no complete calculus for a full probabilistic team logic with the independence atom is on record. The field is a decade old against its siblings' two: beyond the expressivity characterizations, the atomic axiomatizations and the complexity bounds, little is settled.

© 2026 Lingenic LLC