Decidable Fragments of Logics Based on Team Semantics.
Juha Kontinen, Antti Kuusisto, Jonni Virtema · arXiv (Cornell University) · 2014
We study the complexity of variants of dependence logic defined by generalized dependency atoms. Let FOC^2 denote two-variable logic with counting, and let ESO(FOC^2) be the extension of FOC^2 with existential second-order prenex quantification. We show that for any finite collection A of atoms that are definable in ESO(FOC^2), the satisfiability problem of the two-variable fragment of FO(A) is NEXPTIME-complete. We also study satisfiability of sentences of FO(A) in the Bernays-Sch\onfinkel-Ramsey prefix class. Our results show that, analogously to the first-order case, this problem is decidable assuming the atoms in A are uniformly polynomial time computable and closed under substructures. We establish inclusion in 2NEXPTIME. For fixed arity vocabularies, we establish NEXPTIME-completeness.