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