?
О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ
Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2025. Т. 524. № 1. С. 11–18.
Дудаков С. М., Карлов Б. Н.
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.
Гомеоморфизмы топологических пространств называются эквивалентными по надстройке, если надстройки над ними топологически эквивалентны. В частности, топологически сопряженные гомеоморфизмы эквивалентны по надстройке. Известно, что для гомологически неприводимых гомеоморфизмов их топологическая сопряженность является необходимым и достаточным условием их эквивалентности по надстройке. Тогда как инварианты топологической сопряженности гомологически приводимых гомеоморфизмов во многих случаях являются избыточными для эквивалентности по ...
Добавлено: 3 июня 2026 г.
Гнетов Ф. А., Конаков В. Д., Успехи математических наук 2026 Т. 81 № 3 (489) С. 161–162
Пусть M обозначает симметрическое пространство некомпактного типа ранга 1. Опираясь на фундаментальную работу [1], в [2] было показано, что плотность соответствующим образом нормированной суммы независимых Hn-значных случайных величин, определенная через сложение Мёбиуса в модели шара Пуанкаре, сходится к фундаментальному решению соответствующего уравнения теплопроводности. Пределом являлся нормальный закон на Hn, соответствующий ядру теплопроводности, определяемому оператором Лапласа–Бельтрами. ...
Добавлено: 2 июня 2026 г.
Силаков Д. В., Системный администратор 2026 № 3 С. 28–33
В статье про платформы для разработки открытого ПО в Китае мы рассказали про GitCode – молодой проект, позиционируемый как площадка для разработчиков со всего мира. Сейчас на GitCode размещаются проекты, созданные в КНР, но некоторые из них уже известны и на международной арене. Помочь открытым проектам в становлении, развитии и расширению аудитории призван фонд OpenAtom ...
Добавлено: 2 июня 2026 г.
Slivnitsin P., Мыльников Л. А., Engineering Applications of Artificial Intelligence 2026 Vol. 179 Article 115185
Добавлено: 29 мая 2026 г.
Gorbounov Vassily, Kazakov A., Data Analytics and Topology 2025 Vol. 1 No. 1 P. 33–45
Добавлено: 28 мая 2026 г.
Мокиенко О. А., Zisman M. A., Бобров П. Д. и др., American Journal of Physical Medicine and Rehabilitation 2026 Vol. 105 No. 6 P. 555–563
Добавлено: 28 мая 2026 г.
М.: Институт проблем управления им. В.А. Трапезникова РАН, 2024.
В сборник вошли материалы VIII Международной научной конференции «Информационные технологии и технические средства управления» (ICCT-2024). На конференции были рассмотрены вопросы, касающиеся перспектив развития научного приборостроения в телекоммуникационных и управляющих системах, биомедицинской информатики, аппаратного и программного обеспечения информационнокоммуникационных систем, надежности, диагностики и неразрушающего контроля, систем управления и автоматизации, цифровых экосистем, управления производством и логистикой, методов математического ...
Добавлено: 27 мая 2026 г.
Добавлено: 26 мая 2026 г.
Ильяшенко Ю. С., Шилин И. С., Stanislav Minkov, Russian Journal of Mathematical Physics 2026 Vol. 33 No. 1 P. 89–106
Добавлено: 26 мая 2026 г.
Андросов И. А., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 3 P. 87–114
В работе рассматриваются сети эхо-состояний (Echo State Network, ESN), которые являются одними из самых распространенных способов реализации резервуарных вычислений. Они состоят из рекуррентной нейронной сети, веса которой выбираются один раз и не обучаются, и выходного, обычно линейного, обучаемого слоя. Такой подход позволяет создавать энергоэффективные и быстрые нейронные сети, способные обучаться в режиме реального времени. Но ...
Добавлено: 26 мая 2026 г.
Добавлено: 25 мая 2026 г.
Караваева Е. А., Кулигин Л. А., Резуник Л. и др., Труды Института системного программирования РАН 2026 Т. 38 № 3 С. 67–94
В статье представлен метод рефакторинга исходного кода на основе интеграции большой языковой модели (LLM) и расширенной UML-модели программного кода. Предложенный подход позволяет выявлять проблемные участки кода с использованием функций тревожности и структурных метрик классов, а затем выполнять автоматизированный рефакторинг. Ключевой особенностью метода является использование LLM для генерации формальных спецификаций на языке OCL (Object Constraint Language), ...
Добавлено: 24 мая 2026 г.
Добавлено: 23 мая 2026 г.
Zaikin A., Sviridov I., Sosedka A. и др., Technologies 2026 Vol. 14 No. 2 Article 84
Добавлено: 23 мая 2026 г.
Сперанский С. О., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Добавлено: 27 декабря 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Добавлено: 26 ноября 2025 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...
Добавлено: 23 ноября 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.
Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Добавлено: 21 июня 2025 г.
Сапронов Ю. Ф., Юдин Н. Е., Computational Mathematics and Mathematical Physics 2025 Vol. 65 No. 3 P. 567–581
We continue to develop the concept of studying the ε-optimal policy for Average Reward Markov Decision Processes (AMDP) by reducing it to Discounted Markov Decision Processes (DMDP). Existing research often stipulates that the discount factor must not fall below a certain threshold. Typically, this threshold is close to one, and as is well-known, iterative methods ...
Добавлено: 10 июня 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2025 Т. 117 № 1 С. 62–78
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. ...
Добавлено: 3 декабря 2024 г.
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...
Добавлено: 6 декабря 2022 г.
Рыбаков М. Н., Агаджанян И. А., / arXiv. Серия 2211.14571 "Logic". 2022.
Доказывается PSPACE-трудность константных фрагментов всех логик, лежащих между K и wGrz ...
Добавлено: 5 декабря 2022 г.