You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Lecture Notes in Computer Science: CoNP Complexity for Combinations of Non-normal Modal Logics
Contributor:
Dalmonte, Tiziano;
Mazzullo, Andrea
imprint:
Springer Nature Switzerland, 2023
Published in:Lecture Notes in Computer Science
Language:
Not determined
DOI:
10.1007/978-3-031-43513-3_17
ISSN:
0302-9743;
1611-3349
Origination:
Footnote:
Description:
<jats:title>Abstract</jats:title><jats:p>We study the complexity of the validity/derivability problem for combinations of non-normal modal logics in the form of logic fusions, possibly extended with simple interaction axioms. We first present cut-free sequent calculi for these logic combinations. Then, we introduce hypersequent calculi with invertible rules, and show that they allow for a coNP proof search procedure. In the last part of the paper, we consider the case of combinations of logics sharing a universal modality. Using the hypersequent calculi, we show that these logics remain coNP-complete, and also provide an equivalent axiomatisation for them.</jats:p>