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 -