Computer Science Graduate Seminar

Friday, July 23, 2021, 10:00am

Reasoning about Dependence and Independence: Teams and Multiteams

 

Abstract

Team semantics is the mathematical basis of modern logics for reasoning about dependence and independence. Its core feature is that formulae are evaluated against a set of assignments, called a team. This approach dates back to Hodges (1997) who used it to provide a compositional semantics for independence friendly logic. Building on this idea, Väänänen (2007) suggested that dependencies between variables should not be treated as annotations of quantifiers, but as atomic properties of teams. However, being based on sets, team semantics can only be used to reason about the presence or absence of data. Multiteam semantics instead takes multiplicities of data into account and is based on multisets of assignments, called multiteams.

In this talk we give an overview of this formalism, explore a wide spectrum of logics with multiteam semantics and compare them with regard to their expressive power. We exhibit some striking differences between multiteam and team semantics, and also show where these formalisms are similar. Moreover, we present a game-theoretic semantics for our logic and establish connections between logics with multiteam semantics and variants of existential second-order logic.

 

The computer science lecturers invite interested people to join.