The influence of connectivity axiom on complexity of modal logic
We prove that for weakly transitive modal logics equipped with the universal modality whose satisfiability problem is already decidable in PSPACE, adding the connectivity axiom does not increase the complexity. Moreover, we present an algorithm that solves the satisfiability task within the same complexity class.
Authors
- Andrey Kudinov (ORCID: https://orcid.org/0000-0003-0162-2306)
- K. M. Myasnikov
Institutions
- Moscow Institute of Physics and Technology (RU)
Publication Details
- Journal
- Mathematics and Theoretical Computer Science
- Published
- 2025-07-26
- DOI
- https://doi.org/10.26907/2949-3919.2025.2.58-84
- Primary Topic
- Logic, Reasoning, and Knowledge
- Type
- article
- Field-Weighted Citation Impact
- 0.00