Event Detail
Fri Oct 21, 2016 60 Evans Hall 4:10–6 PM |
Logic Colloquium 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.