Team Semantics for Collective Properties and Dependencies

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 266 papers88 conceptsfrozen 2026-10-04

In classical logic, we evaluate whether a formula is true by looking at a single state of the world. In propositional logic, this is a single truth assignment; in modal logic, it is a single "possible world." This approach, known as Tarski semantics, is powerful but has a blind spot: it cannot express properties that emerge only when looking at a collection of states.

Consider the concept of functional dependence. If we want to say "the value of variable $y$ is determined by the value of variable $x$," we cannot verify this by looking at one row in a database. We need to look at the entire table to see if every time $x$ has the same value, $y$ also has the same value. Team semantics provides the mathematical framework for this collective perspective by shifting the unit of evaluation from a single assignment to a set of assignments, called a team.

From Individual Points to Teams

The core intuition behind team semantics, as explored by researchers like Juha Kontinen and Heribert Vollmer, is that a team acts like a relation in a database. In A Fragment of Dependence Logic Capturing Polynomial Time, the authors explain that by evaluating formulas against sets of assignments, logic can track how the value of one variable is determined by others across a collection of data points.

This shift enables the definition of "dependence atoms." A formula like $\text{dep}(x, y)$ is true for a team if, for any two assignments in that team, having the same value for $x$ implies having the same value for $y$. This is inherently a property of the set, not the individuals. As Antti Kuusisto notes in Team Semantics and Recursive Enumerability, this allows logic to characterize complex data relationships and dependencies within a unified structure.

Hyperproperties and System Verification

One of the most impactful applications of this idea is in formal verification. Traditional temporal logics like LTL or CTL check properties of individual execution traces (e.g., "the system never crashes"). However, security requirements often involve hyperproperties—properties that compare multiple execution runs.

For example, "observational determinism" requires that if two runs start with the same public inputs, they must produce the same public outputs, regardless of secret inputs. In Synchronous Team Semantics for Temporal Logics, Andreas Krebs, Jonni Virtema, and Arne Meier demonstrate that by evaluating temporal formulas over sets of traces, we can verify these security requirements more efficiently than with previous path-quantification methods. This approach treats a collection of traces as a single unit of evaluation to capture dependencies across different system executions.

The Logic of Splitting and Collective Choice

Team semantics changes how basic logical operators behave. In classical logic, a disjunction $A \lor B$ is true if the current assignment satisfies $A$ or satisfies $B$. In team semantics, a "tensor" or "split" disjunction requires that the team can be partitioned into two sub-teams, where one sub-team satisfies $A$ and the other satisfies $B$.

This "collective" version of choice is essential for modeling phenomena like "Free Choice" in linguistics. In State-based Modal Logics for Free Choice, the authors use team-based evaluation (referred to as state-based) to explain why "You may have tea or coffee" implies you have the possibility of both. The logic evaluates the statement against a set of possible worlds (an information state), capturing properties that emerge from the distribution of possibilities.

Complexity and Expressive Power

Moving from individuals to teams significantly increases the computational power and complexity of the logic. Miika Hannula and colleagues showed in Complexity of Propositional Logics in Team Semantics that adding classical negation to these logics can elevate the complexity of satisfiability to AEXPTIME-complete.

The expressive power is also vastly expanded. Julian-Steffen Müller and Juha Kontinen proved a version of the Van Benthem Theorem for modal team semantics, showing it captures exactly the fragment of first-order logic invariant under "team bisimulation." Essentially, team semantics allows us to talk about the shape of a distribution of data or states.

Expanding the Horizon: Probabilities and Multiple Relations

The framework has been extended to even more complex data structures:

  • Probabilistic Team Semantics: Arnaud Durand and Jonni Virtema introduced Probabilistic Team Semantics, which replaces sets of assignments with probability distributions. This allows logic to reason about statistical concepts like conditional independence.
  • Polyteam Semantics: In Polyteam Semantics, the authors allow formulas to be evaluated over families of teams. This bridges the gap to multi-relational databases, enabling formal reasoning about dependencies that span across different tables (like foreign key constraints) without needing to flatten them into a single massive table.

By shifting the focus from the individual to the "team," these logics provide a rigorous language for the relational and collective properties that define modern data science, security, and linguistics.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 51 papers
  2. Version 1 · 2026-10-04 · 66 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_team_semantics_861fdd88,
  title = {team semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/team-semantics/rdr_861fdd886b8c4a2ea640e27e917895ec},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_team_semantics_for_collective_properties_861fdd88_v1,
  title = {Team Semantics for Collective Properties and Dependencies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/team-semantics-for-collective-properties-and-dependencies/rdr_861fdd886b8c4a2ea640e27e917895ec/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}