Decidability of predicate logics with team semantics

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 NEXPTIMEcomplete. 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.Academy of FinlandERC/647289Jenny and Antti Wihuri FoundationVilho, Yrjö and Kalle Väisälä Foundatio