Satisfiability of modal inclusion logic: Lax and strict semantics

Lauri Hella; Antti Kuusisto; Arne Meier; Heribert Vollmer

doi:10.1145/3356043

Satisfiability of modal inclusion logic: Lax and strict semantics

Lauri Hella, Antti Kuusisto, Arne Meier, Heribert Vollmer

Computing Sciences

Research output: Contribution to journal › Article › Scientific › peer-review

1 Citation (Scopus)

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	https://doi.org/10.1145/3356043
Publication status	Published - 2019
Publication type	A1 Journal article-refereed

Keywords

Computational complexity
Modal inclusion logic
Satisfiability
Team semantics

Publication forum classification

Publication forum level 2

Access to Document

10.1145/3356043

Cite this

@article{52bcf3eb4f4c4888a0b5007d125c6a98,

title = "Satisfiability of modal inclusion logic: Lax and strict semantics",

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, Computational complexity, Modal inclusion logic, Satisfiability, Team semantics",

author = "Lauri Hella and Antti Kuusisto and Arne Meier and Heribert Vollmer",

note = "DUPL=50949587",

year = "2019",

doi = "10.1145/3356043",

language = "English",

volume = "21",

journal = "ACM TRANSACTIONS ON COMPUTATIONAL LOGIC",

issn = "1529-3785",

number = "1",

}

TY - JOUR

T1 - Satisfiability of modal inclusion logic: Lax and strict semantics

AU - Hella, Lauri

AU - Kuusisto, Antti

AU - Meier, Arne

AU - Vollmer, Heribert

N1 - DUPL=50949587

PY - 2019

Y1 - 2019

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

KW - Computational complexity

KW - Modal inclusion logic

KW - Satisfiability

KW - Team semantics

U2 - 10.1145/3356043

DO - 10.1145/3356043

M3 - Article

AN - SCOPUS:85075599859

SN - 1529-3785

VL - 21

JO - ACM TRANSACTIONS ON COMPUTATIONAL LOGIC

JF - ACM TRANSACTIONS ON COMPUTATIONAL LOGIC

IS - 1

M1 - 7

ER -

Satisfiability of modal inclusion logic: Lax and strict semantics

Abstract

Keywords

Publication forum classification

Access to Document

Fingerprint

Cite this