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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-662-48057-1_22 | Lecture Notes in Computer Science |
Field | DocType | Volume |
NEXPTIME,Discrete mathematics,EXPTIME,Boolean satisfiability problem,Mathematics,Modal,Semantics,Computational complexity theory | Journal | 9234 |
ISSN | Citations | PageRank |
0302-9743 | 9 | 0.66 |
References | Authors | |
5 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lauri Hella | 1 | 331 | 35.67 |
Antti Kuusisto | 2 | 72 | 15.69 |
Arne Meier | 3 | 126 | 19.00 |
Heribert Vollmer | 4 | 805 | 71.64 |