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

Tietotekniikka

Tutkimustuotos: Artikkeli › Tieteellinen › vertaisarvioitu

4 Sitaatiot (Scopus)

Abstrakti

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.

Alkuperäiskieli	Englanti
Artikkeli	7
Julkaisu	ACM TRANSACTIONS ON COMPUTATIONAL LOGIC
Vuosikerta	21
Numero	1
DOI - pysyväislinkit	https://doi.org/10.1145/3356043
Tila	Julkaistu - 2019
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Tutkimusalat

Computational complexity
Modal inclusion logic
Satisfiability
Team semantics

Julkaisufoorumi-taso

Jufo-taso 2

Pääsy asiakirjaan

10.1145/3356043

Siteeraa tätä

@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",

publisher = "Association for Computing Machinery (ACM)",

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

Abstrakti

Tutkimusalat

Julkaisufoorumi-taso

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä