https://www.dagstuhl.de/19031

13. – 18. Januar 2019, Dagstuhl-Seminar 19031

Logics for Dependence and Independence

Organisatoren

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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 9, Issue 1 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

Summary

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.

Summary text license
  Creative Commons BY 3.0 Unported license
  Erich Grädel, Phokion G. Kolaitis, Juha Kontinen, and Heribert Vollmer

Dagstuhl-Seminar Series

Classification

  • Data Structures / Algorithms / Complexity
  • Verification / Logic

Keywords

  • Dependence logic
  • Mathematical logic
  • Computational complexity
  • Finite model theory
  • Game theory

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.