Dagstuhl Seminar 19031
Logics for Dependence and Independence
( Jan 13 – Jan 18, 2019 )
- Erich Grädel (RWTH Aachen, DE)
- Phokion G. Kolaitis (University of California - Santa Cruz, US)
- Juha Kontinen (University of Helsinki, FI)
- Heribert Vollmer (Leibniz Universität Hannover, DE)
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
Dependence and independence are interdisciplinary notions that are ubiquitous in different areas of science. In particular, they appear in such fields as mathematics, computer science, statistics, quantum physics, and game theory. The development of logical and semantical structures for notions of dependence and independence provides an opportunity for a systematic approach, which can expose surprising connections between different areas, and may lead to general results and unifying explanations.
Dependence Logic and, more generally, logics with team semantics are new tools for modeling dependencies and interaction in dynamical scenarios. Reflecting this, dependence logic has higher expressive power and computational complexity than classical logics used for these purposes previously. First-order dependence logic corresponds to the existential fragment of second-order logic; thus, from a computational perspective, dependence logic on finite structures corresponds exactly to the complexity class NP. Since the introduction of dependence logic in 2007, the framework has been generalized in several different directions, including, 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, many central questions remain unanswered so far.
Model theory and complexity for logics with team semantics
The expressive power, as well as the model theoretic and algorithmic properties of dependence logic and its variants, have been studied extensively during the past few years. Recently new variants of dependence logic have been introduced by novel counting constructs and also the consideration of multiteams and approximate dependencies.
These logics are not yet well understood; one of the goals of this Dagstuhl Seminar is to foster a systematic study of the algorithmic and model theoretic properties of various counting mechanisms in team semantics. Another recent development is a descriptive characterization of constraint satisfaction problems by a fragment of dependence logic, which opens new avenues for further research.
Connections to database theory
Database dependencies, such as functional dependencies and inclusion dependencies, are integrity constraints that the data at hand ought to obey. More recently, database dependencies have been used to formalize data inter-operability tasks and to express constraints on ontologies. Dependence logic and its variants elevate database dependencies to “first-class citizens” and make it possible to study the expressive power of database dependencies in a unifying framework. The close relationship between database dependencies and team semantics has already led to fruitful interaction between database theory and dependence logic. Moreover, team semantics has recently been generalized to the aforementioned multiset (multiteam) semantics and also approximate dependencies have been introduced in this framework. Another goal of this seminar is to further enhance the interaction between database theory and dependence logic, and also to explore possible uses of dependence logic in data provenance and in ontology based data access.
Connections to inquisitive semantics, Game Theory, Separation Logic, and Logics of Uncertainty
Inquisitive Semantics is a semantic framework for the analysis of information exchange through communication that is essentially equivalent to team semantics. This connection boosted the development of propositional variants of dependence logic that were well understood in the inquisitive semantics research community. One of the goals of this seminar is to advance the interplay between these closely related frameworks.
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, a forerunner of dependence logic, was first formulated in terms of games only. Games have recently been used to characterize the model checking problem of dependence logic as well as the expressive power of inclusion logic and its counting extension. The connections between game theory and team semantics deserves further study. New potential application areas for team semantics that will be addressed in the seminar include separation logic and logics of uncertainty.
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 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. In addition to addressing the open questions, the seminar also aimed at boosting the exchange of ideas and techniques between dependence logic and its application areas.
Organization of the Seminar and Activities
The workshop brought together 40 researchers from mathematics, 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 workshop, 27 talks of various lengths took place. Introductory and tutorial talks of 90-60 minutes were scheduled prior to the workshop. Most of the remaining slots were filled, mostly with shorter talks, as the workshop commenced. The seminar ended with an open problems and perspectives session. 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 workshop. The presenters and topics were:
- Miika Hannula: Team semantics
- Val Tannen: Provenance
- Dan Suciu: Probabilistic databases
- Meghyn Bienvenu: Constraints in ontology based databases
- David Pym: Resource semantics
- Magdalena Ortiz: Complete and incomplete information in knowledge-enriched databases
- Jef Wijsen: Database repairs
In addition, the seminar consisted of 20 shorter contributed talks, addressing various topics concerning expressibility, axiomatizability, complexity and applications of team-based logics.
The last session of the workshop was devoted to open problems and consisted of contributions by Phokion Kolaitis, Jouko Väänänen and Juha Kontinen presenting questions about decidability and axiomatizability of the implication problem of various fragments of dependence and independence logic, Joachim Biskup addressing decidable first-order prefix classes in the database context, Heribert Vollmer presenting open relationships among various counting classes related to team-based logics, Lauri Hella talking about union-closed properties in Sigma_1^1, and finally Raine Rönnholm addressing relationships between fragments of inclusion logic and greatest fixed-point logic.
The workshop ended with a discussion of future perspectives of the study of logics for dependence and independence.
The workshop 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 workshop 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 workshop.
- Leopoldo Bertossi (Carleton University - Ottawa, CA & RelationalAI Inc., CA) [dblp]
- Dietmar Berwanger (ENS - Cachan, FR) [dblp]
- Meghyn Bienvenu (University of Bordeaux, FR) [dblp]
- Joachim Biskup (TU Dortmund, DE) [dblp]
- Katrin Dannert (RWTH Aachen, DE) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Arnaud Durand (University Paris-Diderot, FR) [dblp]
- Fredrik Engström (University of Göteborg, SE) [dblp]
- Bernd Finkbeiner (Universität des Saarlandes, DE) [dblp]
- Floris Geerts (University of Antwerp, BE) [dblp]
- Erich Grädel (RWTH Aachen, DE) [dblp]
- Gianluca Grilletti (University of Amsterdam, NL) [dblp]
- Miika Hannula (University of Helsinki, FI) [dblp]
- Lauri Hella (Tampere University of Technology, FI) [dblp]
- Åsa Hirvonen (University of Helsinki, FI) [dblp]
- Matthias Hoelzel (RWTH Aachen, DE) [dblp]
- Benny Kimelfeld (Technion - Haifa, IL) [dblp]
- Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
- Juha Kontinen (University of Helsinki, FI) [dblp]
- Paris Koutris (University of Wisconsin - Madison, US) [dblp]
- Sebastian Link (University of Auckland, NZ) [dblp]
- Martin Lück (Leibniz Universität Hannover, DE) [dblp]
- Yasir Mahmood (Leibniz Universität Hannover, DE)
- Arne Meier (Leibniz Universität Hannover, DE) [dblp]
- Magdalena Ortiz (TU Wien, AT) [dblp]
- Martin Otto (TU Darmstadt, DE) [dblp]
- Eric Pacuit (University of Maryland - College Park, US) [dblp]
- Henri Prade (University of Toulouse, FR) [dblp]
- David J. Pym (University College London, GB) [dblp]
- Raine Rönnholm (Tampere University of Technology, FI) [dblp]
- Dan Suciu (University of Washington - Seattle, US) [dblp]
- Val Tannen (University of Pennsylvania - Philadelphia, US) [dblp]
- Bernhard Thalheim (Universität Kiel, DE) [dblp]
- Jouko Väänänen (University of Helsinki, FI) [dblp]
- Jan Van den Bussche (Hasselt University, BE) [dblp]
- Jonni Virtema (Hasselt University, BE) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Jef Wijsen (University of Mons, BE) [dblp]
- Richard Wilke (RWTH Aachen, DE)
- Fan Yang (University of Helsinki, FI) [dblp]
- Dagstuhl Seminar 13071: Dependence Logic: Theory and Applications (2013-02-10 - 2013-02-15) (Details)
- Dagstuhl Seminar 15261: Logics for Dependence and Independence (2015-06-21 - 2015-06-26) (Details)
- Dagstuhl Seminar 24111: Logics for Dependence and Independence: Expressivity and Complexity (2024-03-10 - 2024-03-15) (Details)
- data structures / algorithms / complexity
- verification / logic
- dependence logic
- mathematical logic
- computational complexity
- finite model theory
- game theory