LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Dependence and Independence in Logic
- Date
- Tuesday, June 10 2014 at 11:00AM
- Place
- Auditorium Daniel Chemla (Bât. Institut D'Alembert)
- Speaker
- Erich Grädel (RWTH Aachen)
There have been a number of proposals for incorporating the concepts of dependence or independence into mathematical logic. Classical variants include Henkin quantifiers and independence friendly logics; a more modern approach, triggered by Väänänen's dependence logic, treats notions of dependence and independence as atomic properties and not as annotations of quantifiers, and has motivated the construction and analysis of a large variety of logics based on different notions of dependence and independence, many of which have close connections to dependency concepts from database theory.
The key difference to classical logical formalisms is that dependence and independence manifest themselves not for a single assignment, mapping variables to elements of a structure, but only for a set of such assignments. Accordingly, model-theoretic semantics for logics of dependence and independence refer to structures together with a set of assignments (called a team) and thus differ substantially from the Tarski-style semantics of first-order logic, second-order logic and similar formalisms.
We shall describe different logics of dependence and independence and examine their expressive power. We design model-checking games for logics with team semantics in a general and systematic way. The second-order features of team semantics are reflected by the notion of a consistent winning strategy which is also a second-order notion in the sense that it depends not on single plays but on the space of all plays that are compatible with the strategy. Beyond the application to logics with team semantics, we isolate an abstract, purely combinatorial definition of such games, which may be viewed as second-order reachability games, and study their algorithmic properties. A number of examples are provided that show how logics with team semantics express familiar combinatorial problems in a somewhat unexpected way. Based on our games, we provide a complexity analysis of logics with teams semantics.
We shall also discuss the recently discovered connections between logics with team semantics and fixed-point logics, and analyze these connections in game-theoretic terms.