?
Влияние аксиомы связности на сложность модальной логики.
Математика и теоретические компьютерные науки. 2025. Т. 3. № 2. С. 58–84.
Кудинов А. В., Мясников К. М.
В работе доказывается, что для слабо транзитивных логик с универсальной модальностью, проверку выполнимости формулы для которых можно произвести в PSPACE}, добавление аксиомы связности не увеличивает сложность этой проверки, причем строится явный алгоритм, который решает эту задачу.
Ключевые слова: модальная логикаalgorithmic complexityPSPACEModal LogicUniversal modalityалгоритмическая сложностьconnectedness axiomPSPACEweak transitivityаксиома связностислабая транзитивностьуниверсальная модальность
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Cham: Springer Publishing Company, 2026.
Добавлено: 18 июня 2026 г.
Поддьяков А. Н., Троицкий вариант. Наука 2026 № 12 С. 24–25
В научно-популярной заметке представлен обзор содержания поста филдсовского медалиста Тимоти Гауэрса о возможностях ИИ в математике и содержания комментариев под постом. Обзор сделан в основном чат-ботом DeepSeek. В заключение обсуждается возможность не только решения задач искусственным интеллектом, но и их постановки. ...
Добавлено: 18 июня 2026 г.
Garzón J., Mora Rodríguez J., Морено Ф. Г., Applied Mathematics and Optimization 2026 Vol. 94 No. 10 P. 1–43
Добавлено: 17 июня 2026 г.
Нестеров А. С., Журнал Новой экономической ассоциации 2026
В этой статье рассматривается целевой приём в вузы в России с точки зрения науки об устройстве рынков сочетания и экономических механизмов (matching market and mechanism design), ключевого направления современной теории игр. Мы изучаем механизм целевого приёма -- набор правил, по которым устраивается трёхстороннее сочетание между абитуриентом, заказчиком и образовательной программой. Используемый в России механизм имеет ...
Добавлено: 16 июня 2026 г.
Добавлено: 10 июня 2026 г.
Flamarion M. V., Пелиновский Е. Н., Nonlinear Dynamics 2026 Vol. 114 Article 784
Добавлено: 5 июня 2026 г.
Добавлено: 4 июня 2026 г.
Кузнецов С. Л., Успехи математических наук 2026 Т. 81 № 1(487) С. 137–204
Итерация (звёздочка) Клини – это одна из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. Исследования структур с этой операцией – алгебр Клини и их расширений – начинаются с классического понятия регулярных выражений, задающих формальные языки. Впоследствии были введены так называемые алгебры действий (В. Пратт, 1991 г.; Д. Козен, 1994 г.), или алгебры Клини с делениями. В этих структурах звёздочка Клини сочетается с делениями, согласованными с частичным порядком (такие ...
Добавлено: 4 февраля 2026 г.
Грефенштейн А. В., Сперанский С. О., Математический сборник 2024 Т. 215 № 3 С. 37–69
Разрабатывается кванторная версия пропозициональной модальной логики BK из статьи С. П. Одинцова и Х. Вансинга, в основе которой лежит (немодальная) система Белнапа–Данна; мы будем обозначать эту версию через QBK. Сначала с помощью метода канонических моделей будет доказано, что QBK — как и некоторые важные её расширения — сильно полна относительно подходящей семантики возможных миров. Затем мы ...
Добавлено: 26 декабря 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.
Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Добавлено: 21 июня 2025 г.
Бланк М. Л., Discrete and Continuous Dynamical Systems 2025 Vol. 45 No. 11 P. 4186–4201
Appeals to randomness in various number-theoretic constructions appear regularly in modern scientific publications. Such famous names as V.I. Arnold, M. Katz, Ya.G. Sinai, and T. Tao are just a few examples. Unfortunately, all of these approaches rely on various, although often very non-trivial and elegant, heuristics. A new analytical approach is proposed to address the ...
Добавлено: 23 мая 2025 г.
Добавлено: 10 мая 2023 г.
Черкесова Л. В., Сафарьян О. А., Смирнов И. А., Молодой исследователь Дона 2018 Т. 3 (12) С. 111–121
Представлен проект реализации ρ-метода факторизации Полларда на языке C++, который работает быстрее стандартного алгоритма на 27%. Это помогает значительно облегчить работу в расшифровывании и криптоанализе в различных шифрах, например, таких как RSA. ...
Добавлено: 9 мая 2023 г.
Stepan L. Kuznetsov, Journal of Logic and Computation 2023 Vol. 33 No. 6 P. 1437–1462
Добавлено: 7 марта 2023 г.
Рыбаков М. Н., Агаджанян И. А., / arXiv. Серия 2211.14571 "Logic". 2022.
Доказывается PSPACE-трудность константных фрагментов всех логик, лежащих между K и wGrz ...
Добавлено: 5 декабря 2022 г.
Faliszewski P., Карпов А. В., Obraztsova S., Autonomous Agents and Multi-Agent Systems 2022 Vol. 36 Article 18
Добавлено: 14 марта 2022 г.
Рыбаков М. Н., Александров К. И., Шкатов Д. П., / ArXiv. Серия arXiv:2112.03833 "arXiv:2112.03833". 2021.
В работе показано, что любое произведение нормальных модальных пропозициональных логик, содержащее логику T в качестве сомножителя, погружается в свой фрагмент от одной переменной. Приведённое доказательство является более простой версией аналогичного доказательства, которое готовится к публикации, для произведений и полупроизведений, содержащих в качестве сомножителя логику KTB рефлексивно-симметричных шкал Крипке. ...
Добавлено: 10 декабря 2021 г.
Kikot S., Шапировский И., Золин Е. Е., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 369–388.
Добавлено: 2 декабря 2020 г.
Кузнецов С. Л., , in: Logic, Language, and Security. Essays Dedicated to Andre Scedrov on the Occasion of His 65th BirthdayIssue 12300.: Cham: Springer, 2020. P. 3–16.
Добавлено: 25 ноября 2020 г.