Dagstuhl Seminar 13071
Dependence Logic: Theory and Applications
( Feb 10 – Feb 15, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13071
Organizers
- Samson Abramsky (University of Oxford, GB)
- Juha Kontinen (University of Helsinki, FI)
- Jouko Väänänen (University of Helsinki, FI & University of Amsterdam, NL)
- Heribert Vollmer (Leibniz Universität Hannover, DE)
Contact
- Annette Beyer (for administrative matters)
Schedule
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 and database theory, 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 notions of logical dependence and independence are pervasive, and occur in many areas of science. 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 (e. g., quantum mechanics, social choice theory, and many more), and may lead to useful general results.
One of the main aims of the proposed Dagstuhl Seminar is to bring together, for the first time, researchers working in this area so that they can communicate state-of-the-art advances and embark on a systematic interaction. In particular, bringing together researchers from areas of theoretical studies with the application areas will enhance the synergy between the different communities working on dependence logic.
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 and database theory, 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 notions of logical dependence and independence are pervasive, and occur in many areas of science. 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 (e. g., quantum mechanics, social choice theory, and many more), and may lead to useful general results.
One of the main aims of this Dagstuhl Seminar was to bring together, for the first time, researchers working in this area so that they can communicate state-of-the-art advances and embark on a systematic interaction. In particular, bringing together researchers from areas of theoretical studies with the application areas will enhance the synergy between the different communities working on dependence logic.
Organization of the Seminar and Activities
The workshop brought together 35 researchers from mathematics, theoretical physics, statistics, social choice theory, and theoretical computer science. The participants consisted of both senior and junior researchers, including a number of postdocs and a few advanced graduate students.
Participants were invited to present their work and to communicate state-of-the-art advances. Seventeen talks of various lengths took place over the five days of the workshop. Introductory and tutorial talks of 90-60 minutes were scheduled prior to workshop. Most of the remaining slots were filled, mostly with shorter talks, as the workshop commenced. The organizers considered it important to leave ample free time for discussion.
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. Many attendants expressed their wish for a continuation and stated that this seminar was among the most fruitful Dagstuhl seminars they attended.
Finally, the organizers wish to express their gratitude toward the Scientific Directorate of the Center for its support of this workshop, and hope to establish a series of workshops on Dependence Logic: Theory and Applications in the future.
Creative Commons BY 3.0 Unported license
Samson Abramsky, Juha Kontinen, Jouko Väänänen, and Heribert Vollmer
- Samson Abramsky (University of Oxford, GB) [dblp]
- Dietmar Berwanger (ENS - Cachan, FR) [dblp]
- Olaf Beyersdorff (University of Leeds, GB) [dblp]
- Andreas R. Blass (University of Michigan - Ann Arbor, US) [dblp]
- Julian Bradfield (University of Edinburgh, GB) [dblp]
- Panayiota Constantinou (University of Cambridge, GB)
- Nadia Creignou (University of Marseille, FR) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- A. Philip Dawid (University of Cambridge, GB) [dblp]
- Arnaud Durand (University Paris-Diderot, FR) [dblp]
- Johannes Ebbing (Leibniz Universität Hannover, DE) [dblp]
- Uwe Egly (TU Wien, AT) [dblp]
- Fredrik Engström (University of Göteborg, SE) [dblp]
- Pietro Galliani (University of Helsinki, FI) [dblp]
- Georg Gottlob (University of Oxford, GB) [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]
- Wilfrid Hodges (Okehampton, Devon, GB) [dblp]
- Theo Janssen (University of Amsterdam, NL)
- Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
- Juha Kontinen (University of Helsinki, FI) [dblp]
- Antti Kuusisto (University of Tampere, FI) [dblp]
- Pierfrancesco La Mura (HHL Leipzig, DE) [dblp]
- Sebastian Link (University of Auckland, NZ) [dblp]
- Allen L. Mann (Birkhäuser Science - New York, US) [dblp]
- Arne Meier (Leibniz Universität Hannover, DE) [dblp]
- Eric Pacuit (Tilburg University, NL) [dblp]
- Tero Tulenheimo (University of Lille, FR) [dblp]
- Jouko Väänänen (University of Helsinki, FI & University of Amsterdam, NL) [dblp]
- Jonni Virtema (University of Tampere, FI) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Dag Westerstahl (University of Stockholm, SE) [dblp]
- Fan Yang (University of Helsinki, FI) [dblp]
Related Seminars
- Dagstuhl Seminar 15261: Logics for Dependence and Independence (2015-06-21 - 2015-06-26) (Details)
- Dagstuhl Seminar 19031: Logics for Dependence and Independence (2019-01-13 - 2019-01-18) (Details)
- Dagstuhl Seminar 24111: Logics for Dependence and Independence: Expressivity and Complexity (2024-03-10 - 2024-03-15) (Details)
Classification
- data structures / algorithms / complexity
- verification / logic
Keywords
- dependence logic
- mathematical logic
- computational complexity
- finite model theory
- game theory
