Complexity of Propositional Logics in Team Semantics
Miika Hannula, Juha Kontinen, Jonni Virtema, Heribert Vollmer · arXiv (Cornell University) · 2015
We classify the computational complexity of the satisfiability, validity and model-checking problems for propositional independence, inclusion, and team logic. Our main result shows that the satisfiability and validity problems for propositional team logic are complete for alternating exponential-time with polynomially many alternations.