Details
| Original language | English |
|---|---|
| Article number | 7 |
| Pages (from-to) | 1-18 |
| Number of pages | 18 |
| Journal | ACM Transactions on Computational Logic |
| Volume | 21 |
| Issue number | 1 |
| Early online date | Oct 2019 |
| Publication status | Published - 10 Jan 2020 |
Abstract
We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for the strict and another one for the lax semantics. Both problems turn out to be EXPTIME-complete on general structures. Finally,we showhowfor a specific class of structures NEXPTIME-completeness for these problems under strict semantics can be achieved.
Keywords
- Computational complexity, Modal inclusion logic, Satisfiability, Team semantics
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. 21, No. 1, 7, 10.01.2020, p. 1-18.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Satisfiability of modal inclusion logic
T2 - Lax and strict semantics
AU - Hella, Lauri
AU - Kuusisto, Antti
AU - Meier, Arne
AU - Vollmer, Heribert
N1 - Funding Information: Antti Kuusisto is supported by the European Commission, Community Research and Development Service under Grant No. 647289 “CODA” and the Jenny and Antti Wihuri Foundation. Arne Meier is supported by the Deutsche Forschungsge-meinschaft under Grant No. 247444366 (ME 4279/1-2). Authors’ addresses: L. Hella and A. Kuusisto, Tampere University, Unit of Computing Sciences, Mathematics, Kanslerin-rinne 1 B, Tampere, 33014, Finland; emails: {lauri.hella, antti.kuusisto}@tuni.fi; A. Meier and H. Vollmer, Leibniz Universität Hannover, Institut für Theoretische Informatik, Appelstr. 4, Hannover, 30167, Germany; emails: {meier, vollmer}@thi.uni-hannover.de. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1529-3785/2019/09-ART7 $15.00 https://doi.org/10.1145/3356043
PY - 2020/1/10
Y1 - 2020/1/10
N2 - We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for the strict and another one for the lax semantics. Both problems turn out to be EXPTIME-complete on general structures. Finally,we showhowfor a specific class of structures NEXPTIME-completeness for these problems under strict semantics can be achieved.
AB - We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for the strict and another one for the lax semantics. Both problems turn out to be EXPTIME-complete on general structures. Finally,we showhowfor a specific class of structures NEXPTIME-completeness for these problems under strict semantics can be achieved.
KW - Computational complexity
KW - Modal inclusion logic
KW - Satisfiability
KW - Team semantics
UR - http://www.scopus.com/inward/record.url?scp=85075599859&partnerID=8YFLogxK
U2 - 10.1145/3356043
DO - 10.1145/3356043
M3 - Article
AN - SCOPUS:85075599859
VL - 21
SP - 1
EP - 18
JO - ACM Transactions on Computational Logic
JF - ACM Transactions on Computational Logic
SN - 1529-3785
IS - 1
M1 - 7
ER -