##### Dagstuhl Seminar 15261

### Logics for Dependence and Independence

##### ( Jun 21 – Jun 26, 2015 )

##### Permalink

##### Organizers

- Erich Grädel (RWTH Aachen, DE)
- Juha Kontinen (University of Helsinki, FI)
- Jouko Väänänen (University of Helsinki, FI)
- Heribert Vollmer (Leibniz Universität Hannover, DE)

##### Contact

- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)

##### Schedule

Dependence and independence are interdisciplinary notions that are pervasive in many areas of science. They appear in domains such as mathematics, computer science, statistics, quantum physics, and game theory. The development of logical and semantical structures for these notions provides an opportunity for a systematic approach, which can expose surprising connections between different areas, and may lead to useful general results.

Dependence Logic and more generally logics with team semantics are new tools for modeling dependencies and interaction in dynamical scenarios. Reflecting this, it has higher expressive power and complexity than classical logics used for these purposes previously. Algorithmically, first-order dependence logic corresponds exactly to the complexity class NP and to the so-called existential fragment of second-order logic. Since the introduction of dependence logic in 2007, the framework has been generalized, e.g., to the contexts of modal, intuitionistic, and probabilistic logic. Moreover, interesting connections have been found to complexity theory, database theory, statistics, and dependence logic has been applied in areas such as linguistics, social choice theory, and physics. Although significant progress has been made in understanding the computational side of these formalisms, still many central questions remain unsolved so far.

**Applications of logic with team semantics**

Dependence logic has interesting connections to computer science, linguistics, game theory, social choice theory, philosophy, and physics. It is expected to be very fruitful to bring researchers in fundamental issues together with researchers in the application areas, since this will influence the development of further generalizations and variants of dependence logic. An interesting new connection was made in 2013 when it was realized that the logical framework of so-called Inquisitive Semantics, that analyzes information exchange through communication, is essentially equivalent to the team semantics of dependence logic. This connection boosted the development of propositional variants of dependence logic, which were well understood in the inquisitive semantics research community.

**Model theory for variants of logics with team semantics**

As mentioned above, first-order dependence logic is equal in expressibility to existential second-order logic. With, e.g., the addition of the classical negation or the intuitionistic implication the expressive power of the logic increases up to full second-order logic. However there are variants of dependence logic whose expressive power and many model theoretical properties are not yet well understood. One such example is the so-called first-order inquisitive logic. Other examples come from the area of modal team-based logics, e.g., modal independence logic.

**Complexity issues in logics with team semantics**

For many of the generalizations of dependence logic, basic algorithmic questions such as satisfiability and model checking have not been classified from a computational complexity point of view. Important in this context is the concept of succinctness. E.g., modal dependence logic is known to be equal in expressive power to usual modal logic, however, formulas of the first logic tend to be much shorter than those of the second, which implies a considerable raise in complexity of the satisfiability problem (from PSPACE to NEXPTIME). There are numerous further open complexity issues in team-based logics on Kripke structures such as modal dependence and independence logic.

Also, very little is known at the moment about tractable fragments of dependence logic (except the recent result of Galliani and Hella stating the correspondence between inclusion logic and PTIME). For the applications areas (to be mentioned below) it is very important that the main algorithmic issues (satisfiability, validity, inference, model checking) have efficient solutions. Hence, it is of immense importance to identify fragments of dependence logic and its variants that on the one side allow efficient algorithms and on the other side are still expressive enough for the applications. A seminar as the one proposed here is the ideal opportunity to attack questions like these, since it will bring together researchers working in fundamental areas as well as researchers from the application areas.

**Game theory, category theory, and team-based logics**

The semantics of first-order dependence logic and modal dependence logic can be formulated in game theoretical terms. In fact, historically the semantics of independence friendly logic was first formulated in terms of games only. In 1997, Hodges developed a compositional team semantics for independence friendly logic, the analogue of which is also used for dependence logic. The tight connection between dependence logic and game theory, however, has not been exploited so far from a computational point of view.

Abramsky and Väänänen in a paper from 2009 point out, how many semantical issues in dependence theory can conveniently be formalized and studied in the language of category theory. This connection deserves further study as well.

### Brief Introduction to the Topic

Dependence and independence are interdisciplinary notions that are pervasive in many areas of science. They appear in domains such as mathematics, computer science, statistics, quantum physics, and game theory. The development of logical and semantical structures for these notions provides an opportunity for a systematic approach, which can expose surprising connections between different areas, and may lead to useful general results.

Dependence Logic is a new tool for modeling dependencies and interaction in dynamical scenarios. Reflecting this, it has higher expressive power and complexity than classical logics used for these purposes previously. Algorithmically, first-order dependence logic corresponds exactly to the complexity class NP and to the so-called existential fragment of second-order logic. Since the introduction of dependence logic in 2007, the framework has been generalized, e.,g., to the contexts of modal, intuitionistic, and probabilistic logic. Moreover, interesting connections have been found to complexity theory, database theory, statistics, and dependence logic has been applied in areas such as linguistics, social choice theory, and physics. Although significant progress has been made in understanding the computational side of these formalisms, still many central questions remain unsolved so far.

The Dagstuhl seminar 'Dependence Logic: Theory and Applications' had a major impact to the field of dependence logic opening up connections to new application areas. The aim of this follow-up seminar was to gather together the people working in dependence logic and in the application areas, especially those researchers who have recently started working in this quickly developing area to communicate state-of-the-art advances and embark on a systematic interaction.

### Organization of the Seminar and Activities

The seminar brought together 38 researchers from mathematics, statistics, database theory, natural language semantics, and theoretical computer science. The participants consisted of both senior and junior researchers, including a number of postdocs and advanced graduate students.

Participants were invited to present their work and to communicate state-of-the-art advances. Over the five days of the seminar, 27 talks of various lengths took place. Introductory and tutorial talks of 90-60 minutes were scheduled prior to seminar. Most of the remaining slots were filled, mostly with shorter talks, as the seminar commenced. The organizers considered it important to leave ample free time for discussion.

The tutorial talks were scheduled during the beginning of the week in order to establish a common background for the different communities that came together for the seminar. The presenters and topics were:

- Jouko Väänänen and Juha Kontinen, Dependence Logic
- Bernhard Thalheim, Database Constraints -- A Survey
- Ilya Shpitser, Causal inference
- Lauri Hella, Modal dependence logic
- Ivanio Ciardelli, Dependency as Question Entailment
- Antti Hyttinen, Statistical Independence, Causality and Constraint Satisfaction

There were additionally two introductory talks with a more focused and technical topic:

- Alex Simpson, Sheaf semantics for independence logics
- Phokion Kolaitis, The Query Containment Problem: Set Semantics vs. Bag Semantics

Additionally, the following shorter presentations were given during the seminar:

- Asa Hirvonen, Model theoretic independence
- Kerkko Luosto, Dimensions for Modal Dependence Logic
- Gianluca Paolini, Measure teams
- Olaf Beyersdorff, Proof Complexity of Quantified Boolean Formulas
- Antti Kuusisto, Propositional dependence logic via Kripke semantics
- Johanna Stumpf, Characterisation of the expressive power of modal logic with inclusion atoms
- Sebastian Link, Dependence-driven, non-invasive cleaning of uncertain data
- Jonni Virtema, Complexity of Propositional Inclusion and Independence Logic
- Katsuhiko Sano, Characterizing Frame Definability in Team Semantics via The Universal Modality
- Raine Rönnholm, Expressing properties of teams in k-ary inclusion-exclusion logic
- Julian Bradfield, On the structure of events in Boolean games
- Fan Yang, Some proof theoretical results on propositional logics of dependence and independence
- Erich Grädel, Counting in Team Semantics
- Fredrik Engström, Generalized quantifiers and Dependence Logic
- Miika Hannula, Axiomatizing dependencies in team semantics
- Dietmar Berwanger, An NL-fragment of inclusion logic
- Nicolas de Rugy-Altherre, Tractability Frontier of Data Complexity in Team Semantics

For some of these, an abstract can be found below.

The seminar achieved its aim of bringing together researchers from various related communities to share state-of-the-art research. The organizers left ample time outside of this schedule of talks and many fruitful discussions between participants took place throughout the afternoons and evenings.

### Concluding Remarks and Future Plans

The organizers regard the seminar as a great success. Bringing together researchers from different areas fostered valuable interactions and led to fruitful discussions. Feedback from the participants was very positive as well.

Finally, the organizers wish to express their gratitude toward the Scientific Directorate of the Center for its support of this seminar.

- Faried Abu Zaid (RWTH Aachen, DE) [dblp]
- Dietmar Berwanger (University Paris-Sud - Gif sur Yvette, FR) [dblp]
- Olaf Beyersdorff (University of Leeds, GB) [dblp]
- Julian Bradfield (University of Edinburgh, GB) [dblp]
- Maurice Chandoo (Leibniz Universität Hannover, DE) [dblp]
- Ivano Alessandro Ciardelli (University of Amsterdam, NL) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Nicolas de Rugy-Altherre (University Paris-Diderot, FR) [dblp]
- Arnaud Durand (University Paris-Diderot, FR) [dblp]
- Fredrik Engström (University of Göteborg, SE) [dblp]
- Valentin Goranko (University of Stockholm, SE) [dblp]
- Erich Grädel (RWTH Aachen, DE) [dblp]
- Miika Hannula (University of Helsinki, FI) [dblp]
- Lauri Hella (University of Tampere, FI) [dblp]
- Åsa Hirvonen (University of Helsinki, FI) [dblp]
- Antti Hyttinen (University of Helsinki, FI) [dblp]
- Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
- Juha Kontinen (University of Helsinki, FI) [dblp]
- Antti Kuusisto (Stockholm University, SE) [dblp]
- Sebastian Link (University of Auckland, NZ) [dblp]
- Martin Lück (Leibniz Universität Hannover, DE) [dblp]
- Kerkko Luosto (University of Helsinki, FI & University of Tampere, FI) [dblp]
- Allen L. Mann (University of North Texas, US) [dblp]
- Arne Meier (Leibniz Universität Hannover, DE) [dblp]
- Martin Otto (TU Darmstadt, DE) [dblp]
- Gianluca Paolini (University of Helsinki, FI) [dblp]
- Raine Rönnholm (University of Tampere, FI) [dblp]
- Katsuhiko Sano (JAIST - Ishikawa, JP) [dblp]
- Svenja Schalthöfer (RWTH Aachen, DE) [dblp]
- Thomas Schwentick (TU Dortmund, DE) [dblp]
- Ilya Shpitser (University of Southampton, GB) [dblp]
- Alex Simpson (University of Ljubljana, SI) [dblp]
- Johanna Stumpf (TU Darmstadt, DE) [dblp]
- Bernhard Thalheim (Universität Kiel, DE) [dblp]
- Jouko Väänänen (University of Helsinki, FI) [dblp]
- Jonni Virtema (University of Tampere, FI) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Fan Yang (Utrecht University, NL) [dblp]

##### Related Seminars

##### Classification

- data structures / algorithms / complexity
- verification / logic

##### Keywords

- dependence logic
- mathematical logic
- computational complexity
- finite model theory
- game theory