Logics for Dependence and Independence

Motivation

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.