Decidability of predicate logics with team semantics

Abstract

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-Schönfinkel-Ramsey prefix classes of dependence logic.

Extended version of a MFCS 2016 article. Changes on the earlier arXiv version: title changed, added the result on validity of two-variable dependence logic, restructuring