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 show how for a specific class of structures NEXPTIME-completeness for these problems under strict semantics can be achieved.

Correction of MFCS 2015 paper

References in corpus (2)

• Hierarchies in independence logic
• Modal Independence Logic

Cited by in corpus (1)

• The expressive power of modal logic with inclusion atoms