Arne Meier and Jonni Virtema

Week 2, August 10-14, 2020

Abstract:

During the last decade, there has been a rise of interest in the study of a unified logical theory for the concept of dependence.
A multitude of logics has been introduced in the first-order, propositional, and modal contexts.
The common dominator for these logics is the adaptation of team semantics as a core notion.
These new logics have several applications in many different areas of research such as database theory, linguistics, and philosophy.

The main goal of this course is to introduce a propositional variant of dependence logic and to investigate the computational complexity of satisfiability, validity, and model checking.
The students will acquire technical key observations and techniques in the context of propositional dependence logic which will be useful to improve the overall understanding of complexity, reductions, and algorithms.