Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T19:07:49.068Z Has data issue: false hasContentIssue false

Completing the Picture: Complexity of Graded Modal Logics with Converse

Published online by Cambridge University Press:  27 April 2021

BARTOSZ BEDNARCZYK
Affiliation:
Computational Logic Group, TU Dresden, Dresden, Germany and Institute of Computer Science, University of Wrocław, Wrocław, Poland (e-mail: bartosz.bednarczyk@cs.uni.wroc.pl)
EMANUEL KIEROŃSKI
Affiliation:
Institute of Computer Science, University of Wrocław, Wrocław, Poland (e-mails: emanuel.kieronski@cs.uni.wroc.pl, piotr.witkowski@cs.uni.wroc.pl)
PIOTR WITKOWSKI
Affiliation:
Institute of Computer Science, University of Wrocław, Wrocław, Poland (e-mails: emanuel.kieronski@cs.uni.wroc.pl, piotr.witkowski@cs.uni.wroc.pl)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A complete classification of the complexity of the local and global satisfiability problems for graded modal language over traditional classes of frames has already been established. By “traditional” classes of frames, we mean those characterized by any positive combination of reflexivity, seriality, symmetry, transitivity, and the Euclidean property. In this paper, we fill the gaps remaining in an analogous classification of the graded modal language with graded converse modalities. In particular, we show its NExpTime-completeness over the class of Euclidean frames, demonstrating this way that over this class the considered language is harder than the language without graded modalities or without converse modalities. We also consider its variation disallowing graded converse modalities, but still admitting basic converse modalities. Our most important result for this variation is confirming an earlier conjecture that it is decidable over transitive frames. This contrasts with the undecidability of the language with graded converse modalities.

Information

Type
Original Article
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press