Modal Inclusion Logic: Being Lax is Simpler than Being Strict

Lauri Hella; Antti Johannes Kuusisto; Arne Meier; Heribert Vollmer

doi:10.1007/978-3-662-48057-1_22

Modal Inclusion Logic: Being Lax is Simpler than Being Strict

Lauri Hella, Antti Johannes Kuusisto, Arne Meier, Heribert Vollmer

Department of Applied Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for strict and another one for lax semantics. The complexity of the lax version turns out to be complete for EXPTIME, whereas with strict semantics, the problem becomes NEXPTIME-complete.

Original language	English
Title of host publication	Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015) : Part 1
Editors	Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella
Publisher	Springer
Publication date	2015
Pages	281-292
ISBN (Print)	978-3-662-48056-4
ISBN (Electronic)	978-3-662-48057-1
DOIs	https://doi.org/10.1007/978-3-662-48057-1_22
Publication status	Published - 2015
Event	40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015 - Milan, Italy Duration: 24 Aug 2015 → 28 Aug 2015 Conference number: 40 http://mfcs2015.di.unimi.it/

Conference

Conference	40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015
Number	40
Country/Territory	Italy
City	Milan
Period	24/08/2015 → 28/08/2015
Internet address	http://mfcs2015.di.unimi.it/

Series	Lecture Notes in Computer Science
Volume	9234
ISSN	0302-9743

Access to Document

10.1007/978-3-662-48057-1_22

OpenUrl availability

Full text

Cite this

Hella, Lauri ; Kuusisto, Antti Johannes ; Meier, Arne et al. / Modal Inclusion Logic: Being Lax is Simpler than Being Strict. Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015): Part 1. editor / Giuseppe F. Italiano ; Giovanni Pighizzini ; Donald T. Sannella. Springer, 2015. pp. 281-292 (Lecture Notes in Computer Science, Vol. 9234).

@inproceedings{d379d33c37ca452ca449011ab6811387,

title = "Modal Inclusion Logic: Being Lax is Simpler than Being Strict",

abstract = "We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for strict and another one for lax semantics. The complexity of the lax version turns out to be complete for EXPTIME, whereas with strict semantics, the problem becomes NEXPTIME-complete.",

author = "Lauri Hella and Kuusisto, {Antti Johannes} and Arne Meier and Heribert Vollmer",

year = "2015",

doi = "10.1007/978-3-662-48057-1_22",

language = "English",

isbn = "978-3-662-48056-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "281--292",

editor = "Italiano, {Giuseppe F. } and Pighizzini, {Giovanni } and Sannella, {Donald T. }",

booktitle = "Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015)",

note = "40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, MFCS ; Conference date: 24-08-2015 Through 28-08-2015",

url = "http://mfcs2015.di.unimi.it/",

}

Hella, L, Kuusisto, AJ, Meier, A & Vollmer, H 2015, Modal Inclusion Logic: Being Lax is Simpler than Being Strict. in GF Italiano, G Pighizzini & DT Sannella (eds), Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015): Part 1. Springer, Lecture Notes in Computer Science, vol. 9234, pp. 281-292, 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, Milan, Italy, 24/08/2015. https://doi.org/10.1007/978-3-662-48057-1_22

Modal Inclusion Logic: Being Lax is Simpler than Being Strict. / Hella, Lauri; Kuusisto, Antti Johannes; Meier, Arne et al.
Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015): Part 1. ed. / Giuseppe F. Italiano; Giovanni Pighizzini; Donald T. Sannella. Springer, 2015. p. 281-292 (Lecture Notes in Computer Science, Vol. 9234).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Modal Inclusion Logic: Being Lax is Simpler than Being Strict

AU - Hella, Lauri

AU - Kuusisto, Antti Johannes

AU - Meier, Arne

AU - Vollmer, Heribert

N1 - Conference code: 40

PY - 2015

Y1 - 2015

N2 - We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for strict and another one for lax semantics. The complexity of the lax version turns out to be complete for EXPTIME, whereas with strict semantics, the problem becomes NEXPTIME-complete.

AB - We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for strict and another one for lax semantics. The complexity of the lax version turns out to be complete for EXPTIME, whereas with strict semantics, the problem becomes NEXPTIME-complete.

U2 - 10.1007/978-3-662-48057-1_22

DO - 10.1007/978-3-662-48057-1_22

M3 - Article in proceedings

SN - 978-3-662-48056-4

T3 - Lecture Notes in Computer Science

SP - 281

EP - 292

BT - Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015)

A2 - Italiano, Giuseppe F.

A2 - Pighizzini, Giovanni

A2 - Sannella, Donald T.

PB - Springer

T2 - 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015

Y2 - 24 August 2015 through 28 August 2015

ER -

Hella L, Kuusisto AJ, Meier A, Vollmer H. Modal Inclusion Logic: Being Lax is Simpler than Being Strict. In Italiano GF, Pighizzini G, Sannella DT, editors, Proceedings of the 40th International Symposium Mathematical Foundations of Computer Science (MFCS 2015): Part 1. Springer. 2015. p. 281-292. (Lecture Notes in Computer Science, Vol. 9234). doi: 10.1007/978-3-662-48057-1_22

Modal Inclusion Logic: Being Lax is Simpler than Being Strict

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this