TY - JOUR

T1 - Complexity of propositional logics in team semantic

AU - Vollmer, Heribert

AU - Hannula, Miika

AU - Kontinen, Juha

AU - Virtema, Jonni

N1 - Funding Information: This work was supported by Jenny and Antti Wihuri Foundation and, by grants 292767 and 308712, the Academy of Finland. This work was supported in part by the joint grant by the DAAD (57348395) and the Academy of Finland (308099). DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2018/1

Y1 - 2018/1

N2 - 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.

AB - 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.

KW - Dependence

KW - Inclusion

KW - Independence

KW - Model checking

KW - Propositional logic

KW - Satisfiability

KW - Team semantics

KW - Validity

UR - http://www.scopus.com/inward/record.url?scp=85042515773&partnerID=8YFLogxK

U2 - 10.1145/3157054

DO - 10.1145/3157054

M3 - Article

AN - SCOPUS:85042515773

VL - 19

SP - 2:1-2:14

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

SN - 1529-3785

IS - 1

M1 - 2

ER -