Влияние аксиомы связности на сложность модальной логики.

?

Влияние аксиомы связности на сложность модальной логики.

Математика и теоретические компьютерные науки. 2025. Т. 3. № 2. С. 58–84.

В работе доказывается, что для слабо транзитивных логик с универсальной модальностью, проверку выполнимости формулы для которых можно произвести в PSPACE}, добавление аксиомы связности не увеличивает сложность этой проверки, причем строится явный алгоритм, который решает эту задачу.

Научное направление: Математика

Язык: русский

Полный текст

DOI

Текст на другом сайте

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Разработка системы моделей для сценарного прогнозирования экономического роста и ключевых макропараметров российской экономики, в том числе с привлечением данных экспертных опросов (2025)

2-Elliptic Periodic Orbits near a Nonsimple Homoclinic Tangency in Four-Dimensional Symplectic Maps

Lerman L. M., Turaev D. V., Regular and Chaotic Dynamics 2026 Vol. 31 No. 3 P. 349–369

Добавлено: 15 мая 2026 г.

Bibliometric Analysis by Network Models

Алескеров Ф. Т., Якуба В. И., Khutorskaya O. и др., Springer, 2026.

Добавлено: 15 мая 2026 г.

Neural-network maps for two-parameter modeling of bistability and codimension-two bifurcations in two-dimensional flow dynamical systems

Купцов П. В., Панюшев А. А., Станкевич Н. В., Chaos 2026 Vol. 36 No. 5 Article 053138

Добавлено: 15 мая 2026 г.

Bifurcations and Structural Stability of Generic PC-HC Families

Доровский А. А., / Series arXiv "math". 2026.

Добавлено: 14 мая 2026 г.

The Sobolev space W_2^{1/2}: Simultaneous improvement of functions by a homeomorphism of the circle

Лебедев В. В., Journal of Mathematical Analysis and Applications 2026 Vol. 563 No. 2 Article 130787

Добавлено: 14 мая 2026 г.

Symmetric Cubic Polynomials

Blokh A., Oversteegen L., Selinger N. и др., Arnold Mathematical Journal 2025 Vol. 12 No. 1 P. 1–40

Добавлено: 13 мая 2026 г.

Игры на сетях с линейным наилучшим ответом: модели и методы управления

Петров И. В., Автоматика и телемеханика 2026 № 6 С. 82–118

Системам связанных агентов и сетевому управлению посвящено большое число отечественных и зарубежных исследований. Исторически, наибольший интерес в теории управления возникал к усредняющим системам и, в частности, к задаче консенсуса. Однако сетевое взаимодействие может характеризоваться более специфическими функциями, отражающими зависимость от действий соседей по сети, что особенно явно проявляется в моделях стратегического взаимодействия на сети, которое ...

Добавлено: 12 мая 2026 г.

Архимед: научно-методический сборник

М.: ООО «Макс Пресс», 2026.

В настоящем сборнике представлены тезисы докладов участников семинара "Интеграция основного и дополнительного физико-математического образования", проходившего 11 февраля 2026 года в ГБОУ Школа №2007 ФМШ г. москвы, а также другие публикации, посвящённые вопросам дополнительного физико-математического образования. ...

Добавлено: 11 мая 2026 г.

A two-point phase recovering from holographic data on a single plane

Novikov R., Сивкин В. Н., Inverse Problems 2026 Vol. 42 No. 4 Article 045009

Добавлено: 11 мая 2026 г.

Multivariate Newton interpolation in downward closed spaces reaches the optimal Bernstein–Walsh approximation rate

Hecht M., Hofmann P., Wicaksono D. и др., IMA Journal of Numerical Analysis 2026 Vol. 00 P. 1–30

Добавлено: 11 мая 2026 г.

Weighted Chernoff Information and Optimal Loss Exponent in Context-Sensitive Hypothesis Testing

Кельберт М. Я., Kalimulina E. Y., Entropy 2026 Vol. 28 Article 536

Добавлено: 7 мая 2026 г.

Calogero–Sutherland hyperbolic system and Heckman–Opdam $$\mathfrak {gl}_n$$ gl n hypergeometric function

Белоусов Н. М., Черепанов Л. К., Деркачов С. Э. и др., Selecta Mathematica, New Series 2026 Vol. 32 Article 44

Добавлено: 6 мая 2026 г.

Hodge Laplacian Eigenvalues on Surfaces with Boundary

Муравьев М. Ю., Annales Mathematiques du Quebec 2025

Добавлено: 6 мая 2026 г.

Об изоморфизме задачи Козлова о движении ферромагнетика в магнитном поле и задачи Шоттки о движении четырехмерного твердого тела

Цыганов А. В., Порубов Е. О., Теоретическая и математическая физика 2026 Т. 227 № 2 С. 336–355

Теория тензорных инвариантов обыкновенных дифференциальных уравнений и классификация Картана простых алгебр Ли используется для установления изоморфизма задачи Козлова о движении ферромагнетика в магнитном поле и задачи Шоттки о движении четырехмерного твердого тела. Найдены новые полиномиальные и рациональные бивекторы Пуассона, инвариантные либо относительно пары коммутирующих фазовых потоков, либо относительно одного из пары потоков. ...

Добавлено: 5 мая 2026 г.

Моделирование и оценка ресурсных затрат алгоритмов маршрутизации в сетях на кристалле с двумерной циркулянтной топологией

Монахова Э. А., Монахов О. Г., Рзаев Э. Р. и др., Прикладная дискретная математика 2026 Т. 71 С. 112–127

В настоящей работе исследовано совместное конструирование топологий семейств оптимальных по диаметру циркулянтных сетей $C(N; \pm 1, \pm s_2)$ и реализуемых для них оптимальных алгоритмов маршрутизации сложности $O(1)$. Предлагаемый алгоритм маршрутизации основан на использовании масштабируемых параметров $L$-образных шаблонов плотной укладки графов на плоскости для семейств оптимальных сетей. Определены аналитические формулы зависимости этих параметров от диаметра графов семейств ...

Добавлено: 4 мая 2026 г.

On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces

Дудаков С. М., Lobachevskii Journal of Mathematics 2025 Vol. 46 No. 12 P. 6092–6102

Добавлено: 1 мая 2026 г.

On the minimum number of maximal distance-k independent sets in trees

Талецкий Д. С., / Series arXiv "math". 2026.

Добавлено: 1 мая 2026 г.

Алгоритмическая сложность теорий с итерацией Клини

Кузнецов С. Л., Успехи математических наук 2026 Т. 81 № 1(487) С. 137–204

Итерация (звёздочка) Клини – это одна из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. Исследования структур с этой операцией – алгебр Клини и их расширений – начинаются с классического понятия регулярных выражений, задающих формальные языки. Впоследствии были введены так называемые алгебры действий (В. Пратт, 1991 г.; Д. Козен, 1994 г.), или алгебры Клини с делениями. В этих структурах звёздочка Клини сочетается с делениями, согласованными с частичным порядком (такие ...

Добавлено: 4 февраля 2026 г.

О кванторной версии модальной логики Белнапа–Данна

Грефенштейн А. В., Сперанский С. О., Математический сборник 2024 Т. 215 № 3 С. 37–69

Разрабатывается кванторная версия пропозициональной модальной логики BK из статьи С. П. Одинцова и Х. Вансинга, в основе которой лежит (немодальная) система Белнапа–Данна; мы будем обозначать эту версию через QBK. Сначала с помощью метода канонических моделей будет доказано, что QBK — как и некоторые важные её расширения — сильно полна относительно подходящей семантики возможных миров. Затем мы ...

Добавлено: 26 декабря 2025 г.

Two Types of Filtrations for wK4 and Its Relatives

Кудинов А. В., Shapirovsky I., Studia Logica 2025 P. 1–25

Добавлено: 14 октября 2025 г.

Логики с аксиомой конвергентности: сложность при малом числе переменных в языке

Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.

Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...

Добавлено: 21 июня 2025 г.

Сложность константных фрагментов ненормальных модальных логик

Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.

Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...

Добавлено: 21 июня 2025 г.

Are prime numbers and quadratic residues random?

Бланк М. Л., 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 г.

Modification and Optimization of Pollards's Factorization ρ-Method by Means of Recursive Algorithm of Number Calculation Factorization

Смирнов И. А., Разумов П. В., Болдырихин Н. В. и др., IEEE, 2019.

Добавлено: 10 мая 2023 г.