Satisfiability of modal inclusion logic: Lax and strict semantics

Lauri Hella, Antti Kuusisto, Arne Meier, Heribert Vollmer

Tutkimustuotos: ArtikkeliScientificvertaisarvioitu

1 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äiskieliEnglanti
Artikkeli7
JulkaisuACM TRANSACTIONS ON COMPUTATIONAL LOGIC
Vuosikerta21
Numero1
DOI - pysyväislinkit
TilaJulkaistu - 2019
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Tutkimusalat

  • Computational complexity
  • Modal inclusion logic
  • Satisfiability
  • Team semantics

Julkaisufoorumi-taso

  • Jufo-taso 2

Sormenjälki

Sukella tutkimusaiheisiin 'Satisfiability of modal inclusion logic: Lax and strict semantics'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä