Дудаков Сергей Михайлович
Факультет математики
Профессиональные интересы
Должности
- профессор — Факультет математики
Био
- · Начал работать в НИУ ВШЭ в 2023 году.
Образование
- 2025 · Ученое звание: Профессор
- 2008 · Доктор физико-математических наук
- 2004 · Ученое звание: Доцент
- 1997 · Специалитет: Тверской государственный университет, специальность «Прикладная математика», квалификация «Математик»
Опыт работы
- · 2023: Профессор Факультета математики с года
Идентификаторы исследователя
- ORCID:
0000-0003-2659-265X - ResearcherID:
B-2740-2014 - SPIN РИНЦ:
2474-9802 - Google Scholar: https://scholar.google.com/citations?user=ZCRpNcEAAAAJ&hl=en
- Scopus AuthorID:
6507617497
Публикации (14)
О теории решеток подалгебр для произвольных группоидов
2026 · ARTICLE · ru
В статье исследуется теория решеток подалгебр для класса произвольных группоидов – алгебр, содержащих бинарную операцию. Ранее было доказано, что аналогичные теории решеток для классов абелевых групп, всех групп, моноидов и полугрупп позволяют интерпретировать элементарную арифметику. Следовательно, они неразрешимы и не имеют рекурсивной аксиоматизации. Вопрос о теории решеток для класса всех группоидов оставался открытым, так как доказательство использовало ассоциативность бинарной операции. В настоящей работе мы используем метод, который позволяет обойти это ограничение, он применим к произвольным группоидам. Это доказывает возможность интерпретации элементарной арифметики в теории решеток подалгебр для класса всех группоидов. Значит, теория решеток подалгебр для класса всех группоидов алгоритмически неразрешима и не имеет рекурсивной аксиоматизации. Также мы приводим некоторые результаты о верхней оценке степени неразрешимости теорий решеток группоидов. Библиография: 12 названий.
ПРОБЛЕМЫ АЛГОРИТМИЧЕСКОЙ РАЗРЕШИМОСТИ И АКСИОМАТИЗАЦИИ АЛГЕБРЫ КОНЕЧНЫХ ПОДМНОЖЕСТВ ДЛЯ БИНАРНЫХ ОПЕРАЦИЙ
2025 · ARTICLE · ru
Рассматриваются алгебры конечных подмножеств, когда исходная алгебра является бесконечным группоидом. Доказывается, что для линейных пространств над полями конечной характеристики теория построенной алгебры алгоритмически эквивалентна элементарной арифметике. Далее этот результат обобщается на произвольные бесконечные абелевы группы. В качестве следствия получается, что общая теория классов всех алгебр конечных подмножеств имеет степень неразрешимости, не меньшую чем элементарная арифметика, для широкого круга исходных алгебр: абелевых групп, произвольных групп, моноидов, полугрупп, группоидов. Это также доказывает невозможность рекурсивной аксиоматизации теорий таких классов. Другим следствием является неразрешимость и невозможность рекурсивной аксиоматизации теории решетки подалгебр для абелевых групп конечной экспоненты, а также теорий классов таких решеток для групп, моноидов и полугрупп.Библиография: 17 наименований.
О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ
2025 · ARTICLE · ru
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.
О теориях алгебр подмножеств и решёток подпространств в конечных линейных пространствах
2025 · ARTICLE · ru
В наших предыдущих работах мы видели, что теории фигур и подпространств для бесконечных линейных пространств имеют высокую степень неразрешимости: они допускают интерпретацию элементарной арифметики, а в случае бесконечных фигур - даже арифметики второго порядка. В случае конечных линейных пространств эти утверждения конечно же неверны, так как мы можем построить алгоритм, перебирающий все конечные линейные пространства и выдающий все формулы, модель которых нашлась. Следовательно, для конечных линейных пространств теории фигур и подпространств принадлежат классу Π1 - дополнений рекурсивно перечислимых множеств. В настоящей работе мы показываем, что эти теории являются полными задачами для класса Π1, то есть по"=прежнему неразрешимы и не рекурсивно аксиоматизируемы.
On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces
2025 · ARTICLE · en
We study the additive theory of arbitrary figures in linear spaces, that is, the theory of addition extended to sets of vectors. Our main result is the following: if a linear space is infinite, then the additive theory of figures admits interpreting second-order arithmetic and, therefore, it has such or higher degree of undecidability. For countably infinite spaces, we prove the opposite result: the theory of figures can be interpreted in second-order arithmetic. Therefore, these theories are algorithmically equivalent. For uncountable spaces, the last question remains open. For spaces of different cardinalities, we show that the additive theories of figures can be elementary non- equivalent. Then, we consider the case of countable figures only. In this case, we prove a variant of the Löwenheim–Skolem theorem. At last, we establish the exact undecidability degree that also corresponds to second-order arithmetic for original spaces of any infinite cardinality that is not less than continuum.
О МОНОИДЕ С РАЗРЕШИМОЙ ТЕОРИЕЙ КОНЕЧНЫХ ПОДМНОЖЕСТВ
2024 · ARTICLE · ru
В наших предыдущих работах мы продемонстрировали, что теория конечных подмножеств различных ассоциативных алгебр позволяет интерпретировать элементарную арифметику, в частности, она неразрешима. Например, это было показано для любых бесконечных абелевых групп. Возникает естественный вопрос: можно ли обобщить этот результат на более широкий класс алгебр, скажем, все коммутативные моноиды. В некоторых случаях нами ответ тоже получен ранее: для коммутативных моноидов с сокращением, имеющим элемент бесконечного порядка или произвольных абелевых групп. Сейчас же мы продемонстрируем, что не для всяких коммутативных моноидов это верно. Более того, мы дадим описание конструкции, которая позволяет строить такого рода системы из разного рода исходных алгебр. Вместе с тем, будут указаны и некоторые границы её применимости.
О степени неразрешимости теории фигур в линейных пространствах
2024 · ARTICLE · ru
Мы изучаем аддитивную теорию произвольных фигур в линейных пространствах, т.е. теорию множеств точек/векторов, на которые естественным образом распространена операция сложения. Наш основной результат: если линейное пространство бесконечно, то аддитивная теория фигур в нем позволяет интерпретировать арифметику второго порядка и, следовательно, имеет не меньшую степень неразрешимости. Для счетно бесконечных пространств мы доказываем обратный результат: теория фигур в них может быть проинтерпретирована в арифметике второго порядка, следовательно, две такие теории алгоритмически эквивалентны. Для несчетных пространств последний вопрос остается открытым; мы показываем, что для пространств разных мощностей аддитивные теории фигур в них могут не быть элементарно эквивалентны.
РАЗРЕШИМОСТЬ ТЕОРИИ КОНЕЧНЫХ ПОДМНОЖЕСТВ БЕЗАТОМНЫХ БУЛЕВЫХ АЛГЕБР
2023 · ARTICLE · ru
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория построенной таким образом новой системы сводится к теории безатомных булевых алгебр. Следовательно, также как и теория исходной системы, теория новой системы оказывается разрешимой.
ON UNDECIDABILITY OF FINITE SUBSETS THEORY FOR TORSION ABELIAN GROUPS
2022 · ARTICLE · en
Let M be a commutative cancellative monoid with an element of infinite order. The binary operation can be extended to all finite subsets of M by the pointwise definition. So, we can consider the theory of finite subsets of M. Earlier, we have proved the following result: in the theory of finite subsets of M elementary arithmetic can be interpreted. In particular, this theory is undecidable. For example, the free monoid (the sets of all words with concatenation) has this property, the corresponding algebra of finite subsets is the theory of all finite languages with concatenation. Another example is an arbitrary Abelian group that is not a torsion group. But the method of proof significantly used an element of infinite order, hence, it can't be immediately generalized to torsion groups. The compactness is not applicable here because the theories of subsets can differ for elementary equivalent source algebras. In this paper we prove the given theorem for Abelian torsion groups those have elements of unbounded order.
Лекции по дискретной математике
2021 · BOOK · ru
Учебник содержит лекционный материал по дисциплине "Дискретная математика", а также примеры задач с решениями и задачи для самостоятельной работы. Основные разделы учебника: множества, математическая индукция, комбинаторика, булевы функции, логика высказываний и предикатов, графы, автоматы и формальные языки, алгоритмы. Учебник адресован, прежде всего, студентам младших курсов, обучающихся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные и информационные науки", 09.03.00 "Информатика и вычислительная техника".
Курсы (2)
-
Научно-исследовательский семинар "Логика и алгоритмы"
2025/2026 · Бакалавриат · рус
-
Логика и алгоритмы · 2 раза
2024/2025, 2023/2024 · Бакалавриат · рус