The Entailment Problem in Modal and Propositional Dependence Logics.
Miika Hannula · arXiv (Cornell University) · 2016
We examine the entailment problem for different modal and propositional dependence logics defined in terms of dependence, independence, or inclusion atoms. We establish numerous new complexity results, and settle a long-standing open question by showing that the validity problem for modal dependence logic is NEXPTIME-complete.