Tampere University of Technology

TUTCRIS Research Portal

Satisfiability of modal inclusion logic: Lax and strict semantics

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Article number7
JournalACM TRANSACTIONS ON COMPUTATIONAL LOGIC
Volume21
Issue number1
DOIs
Publication statusPublished - 1 Oct 2019
Publication typeA1 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.

Keywords

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

Publication forum classification

Field of science, Statistics Finland