Informatik-Oberseminar: Richard Wilke: Reasoning about Dependence and Independence: Teams and Multiteams
Freitag, 23.07.2021, 10.00 Uhr
Vortragender: Richard Wilke
Reasoning about Dependence and Independence: Teams and Multiteams
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.