Дудаков Сергей Михайлович
Факультет математики
Профессиональные интересы
Должности
- профессор — Факультет математики
Био
- · Начал работать в НИУ ВШЭ в 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)
ЗАДАЧНИК ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
2021 · BOOK · ru
Учебное пособие адресовано изучающим курс дискретной математики, прежде всего, студентам младших курсов, обучающимся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные и информационные науки", 09.03.00 "Информатика и вычислительная техника". Настоящий сборник задач является пособием для практических занятий по некоторым разделам дискретной математики и может быть использован преподавателями и студентами для подготовки к семинарским занятиям и контрольным работам. В книгу вошло более шестисот задач и упражнений, многие из которых состоят из нескольких независимых подзадач. Почти все задачи снабжены ответами, а многие более сложные задачи - указаниями или решениями.
On Undecidability of Subset Theory for Some Monoids
2021 · ARTICLE · en
Early we (with B. N. Karlov) have proved the following claim for the infinite cyclic monoid H. Let exp H be an algebra of finite subsets of H with the same operation, exp H must be a monoid again. So the theory of exp H is equivalent to elementary arithmetic. Thus, the theory of the monoid exp H is undecidable. Here we consider an arbitrary commutative cancellative monoid with an element of infinite order, and generalize the previous claims to the corresponding monoid exp H.
COMPLEXITY OF LAMBEK CALCULI WITH MODALITIES AND OF TOTAL DERIVABILITY IN GRAMMARS
2021 · ARTICLE · en
The Lambek calculus with the unit can be defined as the atomic theory (algebraic logic) of the class of residuated monoids. This calculus, being a theory of a broader class of algebras than Heyting ones, is weaker than intuitionistic logic. Namely, it lacks structural rules: permutation, contraction, and weakening. We consider two extensions of the Lambek calculus with modalities—the exponential, under which all structural rules are permitted, and the relevant modality, under which only permutation and contraction rules are allowed. The Lambek calculus with a relevant modality is used in mathematical linguistics. Both calculi are algorithmically undecidable. We consider their fragments in which the modality is allowed to be applied to just formulas of Horn depth not greater than 1. We prove that these fragments are decidable and belong to the NP class. To show this, in the case of a relevant modality, we introduce a new notion of ℛ-total derivability in context-free grammars, i.e., existence of a derivation in which each rule is used at least a given number of times. It is stated that the ℛ-totality problem is NP-hard for context-free grammars. Also we pinpoint algorithmic complexity of ℛ-total derivability for more general classes of generative grammars.
On Decidability of Theories of Regular Languages
2021 · ARTICLE · en
This paper is dedicated to studying decidability properties of theories of regular languages with classical operations: union, concatenation, and the Kleene star. The theory with union only is a theory of some Boolean algebra, so it is decidable. We prove that the theory of regular languages with the Kleene star only is decidable. If we use union and concatenation simultaneously, then the theory becomes both Σ1- and π1-hard over the one-symbol alphabet. Using methods from the proof of this theorem we establish that the theory of regular languages over one-symbol alphabet with union and the Kleene star is as hard as arithmetic. Then we establish that the theory with all three operations is reducible to arithmetic also, hence, it is equivalent to arithmetic. Finally, we prove that the theory of regular languages over any alphabet with concatenation only is equivalent to arithmetic also. The last result is based on our previous work where an analogous theorem was proved for one-symbol languages.
Курсы (2)
-
Научно-исследовательский семинар "Логика и алгоритмы"
2025/2026 · Бакалавриат · рус
-
Логика и алгоритмы · 2 раза
2024/2025, 2023/2024 · Бакалавриат · рус