The influence of connectivity axiom on complexity of modal logic
https://doi.org/10.26907/2949-3919.2025.2.58-84
Abstract
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.
About the Authors
K. M. Myasnikov
Moscow Institute of Physics and Technology
Russian Federation
Konstantin Maksimovich Myasnikov
Russian Federation
Konstantin Maksimovich Myasnikov
9 Institutskii av., Dolgoprudny 141701
A. V. Kudinov
Moscow Institute of Physics and Technology
Russian Federation
Andrey Valerievich Kudinov
Russian Federation
Andrey Valerievich Kudinov
9 Institutskii av., Dolgoprudny 141701
References
1. V. Goranko, Modal definability in enriched languages, Notre Dame J. Formal Logic 31 (1), 81–105 (1990). DOI: https://doi.org/10.1305/ndjfl/1093635335
2. V. Shehtman, “Everywhere” and “here”, J. Appl. Non-Classical Logics 9 (2–3), 369–379 (2012). DOI: https://doi.org/10.1080/11663081.1999.10510972
3. E. Hemaspaandra, The price of universality. Combining logics, Notre Dame J. Formal Logic 37 (2), 174–203 (1996). DOI: https://doi.org/10.1305/ndjfl/1040046086
4. I. Shapirovsky, Satisfiability problems on sums of Kripke frames, ACM Trans. Comput. Log. 23 (3), art. 15 (2022). DOI: https://doi.org/10.1145/3508068
5. A. Chagrov, M. Zakharyaschev, Modal Logic, in: Oxford Logic Guides 35, The Clarendon Press, Oxford University Press, New York, 1997.
6. L. Esakia, Weak transitivity – a restitution, Logical Investigations 8, 244–255, (2001) [in Russian]. URL: https://logicalinvestigations.ru/article/view/186
7. G. Bezhanishvili, L. Esakia, D. Gabelaia, Spectral and T0-spaces in d-semantics, in: Lecture Notes in Comput. Sci. 6618, Springer, Heidelberg, 16–29, 2011. DOI: https://doi.org/10.1007/978-3-642-22303-7_2
8. P. Blackburn, M. de Rijke, Y. Venema, Modal Logic, in: Cambridge Tracts in Theoretical Computer Science 53, Cambridge Univ. Press, Cambridge, 2001. DOI: https://doi.org/10.1017/CBO9781107050884
9. S. Arora, B. Barak, Computational complexity. A modern approach, Cambridge Univ. Press, Cambridge, 2009. DOI: https://doi.org/10.1017/CBO9780511804090
Review
For citations:
Myasnikov K.M., Kudinov A.V. The influence of connectivity axiom on complexity of modal logic. Mathematics and Theoretical Computer Science. 2025;3(2):58-84. (In Russ.) https://doi.org/10.26907/2949-3919.2025.2.58-84
Views:
136
Email this article 