Complexity Results in Team Semantics: Nonemptiness Is Not So Complex

Authors:
  • AAAleksi Anttila
    Aleksi Anttila
  • JKJuha Kontinen
    Juha Kontinen
  • FYFan Yang
    Fan Yang
Preprint
Publisher website
Google Scholar
Abstract
We initiate the study of the complexity-theoretic properties of convex logics in team semantics. We focus on the extension of classical propositional logic with the nonemptiness atom NE, a logic known to be both convex and union closed. We show that the satisfiability problem for this logic is NP-complete, that its validity problem is coNP-complete, and that its model-checking problem is in P.