Satisfiability of modal inclusion logic: Lax and strict semantics
Research output: Contribution to journal › Article › Scientific › peer-review
Details
Original language | English |
---|---|
Article number | 7 |
Journal | ACM TRANSACTIONS ON COMPUTATIONAL LOGIC |
Volume | 21 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Oct 2019 |
Publication type | A1 Journal article-refereed |
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.
ASJC Scopus subject areas
Keywords
- Computational complexity, Modal inclusion logic, Satisfiability, Team semantics