Decidability of predicate logics with team semantics
Juha Kontinen, Antti Kuusisto, Jonni Virtema · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIME-complete. Furthermore, we show that the validity problem of two-variable dependence logic is undecidable, thereby solving an open problem from the team semantics literature. We also briefly analyse the complexity of the Bernays-Schoenfinkel-Ramsey prefix classes of dependence logic.