Fri Oct 21, 2016
60 Evans Hall, 4:10–6 PM
Erich Grädel (RWTH Aachen University)
Back and Forth Between Team Semantics, Games, and Tarski Semantics
Team semantics, due to Wilfrid Hodges, is the mathematical basis of modern logics of dependence and independence in which, following a proposal by Väänänen, dependencies are considered as atomic statements, and not as annotations of quantifiers. In team semantics, a formula is evaluated not against a single assignment of values to the free variables, but against a set of such assignments.
Logics with team semantics have strong expressive power and some surprising properties. They can be analyzed in several different ways. First-order formulae with team semantics and dependencies can be translated into sentences of existential second-order logic, with an additional predicate for the team (and with classical Tarski semantics). We can thus understand the power of a specific logic of dependence or independence by identifying the fragment of existential second-order logic to which it corresponds. Further, logics can be understood through their games. In general the model-checking games for logics with team semantics turn out to be second-order reachability games.
We shall then have a closer look at the specific case of logics with inclusion dependencies, and reveal their connection with safety games and logics with greatest fixed-points.