Computer Science Graduate Seminar
Friday, July 23, 2021, 10:00am
Reasoning about Dependence and Independence: Teams and Multiteams
- Richard Wilke, M.Sc. – Research Group Mathematical Foundations of Computer Science
- Zoom: https://rwth.zoom.us/j/97181863376?pwd=VmZIUzlNTXhQRFl0S25uRFBTRW0wdz09
Meeting ID: 971 8186 3376
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.