2026-07-24T00:44:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6472 2024-03-06T10:38:22Z ddc:004 open_access

Decidability of Predicate Logics with Team Semantics Kontinen, Juha Kuusisto, Antti Virtema, Jonni team semantics dependence logic complexity two-variable logic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juha Kontinen and Antti Kuusisto and Jonni Virtema 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.60 urn:nbn:de:0030-drops-64726 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.60 eng https://creativecommons.org/licenses/by/3.0/legalcode