Влияние аксиомы связности на сложность модальной логики
https://doi.org/10.26907/2949-3919.2025.2.58-84
Аннотация
Доказывается, что для слабо транзитивных логик с универсальной модальностью, проверку выполнимости формулы для которых можно произвести в PSPACE, добавление аксиомы связности не увеличивает сложность этой проверки, причем строится явный алгоритм, который решает эту задачу.
Об авторах
К М. Мясников
Московский физико-технический институт
Россия
Константин Максимович Мясников
Россия
Константин Максимович Мясников
Институтский переулок, д. 9, Долгопрудный, 141701
А. В. Кудинов
Московский физико-технический институт
Россия
Андрей Валерьевич Кудинов
Россия
Андрей Валерьевич Кудинов
Институтский переулок, д. 9, Долгопрудный, 141701
Список литературы
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. Л. Эсакиа, Слабая транзитивность – реституция, Логические исследования 8, 244–255 (2001). 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
Рецензия
Для цитирования:
Мясников К.М., Кудинов А.В. Влияние аксиомы связности на сложность модальной логики. Математика и теоретические компьютерные науки. 2025;3(2):58-84. https://doi.org/10.26907/2949-3919.2025.2.58-84
For citation:
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
Просмотров:
34
Послать статью по эл. почте 