TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Satisfiability of modal inclusion logic: Lax and strict semantics

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Artikkeli7
JulkaisuACM TRANSACTIONS ON COMPUTATIONAL LOGIC
Vuosikerta21
Numero1
DOI - pysyväislinkit
TilaJulkaistu - 1 lokakuuta 2019
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.

Tutkimusalat

Julkaisufoorumi-taso

Tilastokeskuksen tieteenalat