Details
| Original language | English |
|---|---|
| Article number | 2 |
| Pages (from-to) | 2:1-2:14 |
| Number of pages | 14 |
| Journal | ACM Transactions on Computational Logic |
| Volume | 19 |
| Issue number | 1 |
| Early online date | 6 Jan 2018 |
| Publication status | Published - Jan 2018 |
Abstract
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.
Keywords
- Dependence, Inclusion, Independence, Model checking, Propositional logic, Satisfiability, Team semantics, Validity
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- Mathematics(all)
- Logic
- Mathematics(all)
- Computational Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: ACM Transactions on Computational Logic, Vol. 19, No. 1, 2, 01.2018, p. 2:1-2:14.
Research output: Contribution to journal › Article › Research › peer review
}
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 -