?
О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ
Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2025. Т. 524. № 1. С. 11–18.
Дудаков С. М., Карлов Б. Н.
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.
Мизинов П. В., Journal of Computer Virology and Hacking Techniques 2023 No. 20 P. 383–396
Системы биометрического распознавания вен уязвимы для атак типа «биометрическое предъявление». Традиционно исследователи использовали изображение сосудистого русла пользователя, полученное в ближнем инфракрасном диапазоне (БИК), для создания инструмента атаки на биометрическое предъявление (ИАБП). В данной статье исследуется возможность использования свободного программного обеспечения для сбора данных о венозном рисунке кисти без использования БИК при нормальном освещении и создания ...
Добавлено: 11 августа 2026 г.
Добавлено: 11 августа 2026 г.
Трубочкина Н. К., М.: Издательство «Юрайт», 2026.
Учебник посвящен формированию у студентов целостного представления о современных производственных процессах и методах их анализа и управления на основе технологий машинного обучения. В условиях четвертой промышленной революции, когда традиционные инженерные дисциплины неразрывно переплетаются с интеллектуальными методами обработки данных, возникает потребность в специалистах, способных интегрировать знания из обеих областей. Настоящий учебник призван удовлетворить эту потребность, предлагая ...
Добавлено: 8 августа 2026 г.
Kulev Y., Максаев А. М., Промыслов В. В., Linear Algebra and its Applications 2026 Vol. 730 P. 51–72
Добавлено: 7 августа 2026 г.
Kanunnikov A., Промыслов В. В., Vassilieva E., Electronic Journal of Combinatorics 2024 Vol. 31 No. 3 Article P3.6
Добавлено: 7 августа 2026 г.
Spiridonov V. P., Belousov N. M., Sarkissian G. A., Analysis and Mathematical Physics 2026 Vol. 16 Article 96
Добавлено: 4 августа 2026 г.
Гайфуллин С. А., Киктева В. В., Results in Mathematics 2026 Vol. 81 No. 5 Article 146
Добавлено: 3 августа 2026 г.
Лунц В. А., Функциональный анализ и его приложения 2026 Т. 60 № 3 С. 127–129
Доказано, что канонические полуортогональные разложения производной категории диаграммной схемы индуцируют аналогичные разложения подкатегории совершенных комплексов. ...
Добавлено: 3 августа 2026 г.
Беломестный Д. В., Гасников А. В., Гладин Е. Л. и др., Russian Mathematical Surveys 2026 Vol. 81 No. 4(490) P. 3–90
Добавлено: 3 августа 2026 г.
Чеповский А. М., М.: Мастерская Печати Идей, 2026.
В учебном пособии представлены методы и алгоритмы автоматического анализа корпусов текстов на естественных языках. Предназначено для изучающих методов обработки текстов на естественных языках и создания обучающих массивов текстов.
Для студентов, аспирантов и научных работников, изучающих методы компьютерной лингвистики и обработку текстов. ...
Добавлено: 1 августа 2026 г.
Абызов А. Н., Буутай П. Н., Математика и теоретические компьютерные науки 2026 Т. 4 № 2 С. 4–75
Статья носит обзорно-методический характер и посвящена развитию идей Е.И. Золотарёва, заложенных в его подходе к доказательству квадратичного закона взаимности (1872 г.). Мы рассматриваем расширения подхода Золотарёва на абстрактные числовые кольца, приведенные в работе А. Бруньята и П.Л. Кларка (2015 г.), и на конечные группы, изученные в статье У. Дьюка и К. Хопкинс (2005 г.). Также ...
Добавлено: 30 июля 2026 г.
Уилкокс П., Романов А. Ю., М.: ДМК Пресс, 2025.
Книга, которую вы держите в руках, продолжает серию «Книжная полка истового
инженера», которая издается при поддержке компании YADRO.
Данная книга представляет собой учебник по теоретическим основам продвинутой
функциональной верификации и содержит лучшие практики, используемые в настоящее
время. В ней подробно описана унифицированная методология верификации
(UVM) и раскрыты такие темы, как функциональный виртуальный прототип, функциональное
покрытие, утверждения, формальная верификация, тестбенчи, косимуляция,
эмуляция, аппаратное ...
Добавлено: 30 июля 2026 г.
Mikhaylets E. V., Razorenova A. М., Chernyshev V. L. и др., Scientific Reports 2026 Vol. 16 Article 23560
Добавлено: 29 июля 2026 г.
Добавлено: 28 мая 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 г.