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.
| Original language | English |
|---|---|
| Article number | 7 |
| Journal | ACM TRANSACTIONS ON COMPUTATIONAL LOGIC |
| Volume | 21 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2019 |
| Publication type | A1 Journal article-refereed |
Funding
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 [email protected]. © 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
Keywords
- Computational complexity
- Modal inclusion logic
- Satisfiability
- Team semantics
Publication forum classification
- Publication forum level 2