Окончил Тверской госуниверситет по специальности "Прикладная
математика", получил квалификацию "Математик".
После окончания Тверского госуниверситета в 1997-2000 годах
работал в университете ассистентом кафедры информатики.
В 2000 г. защитил кандидатскую диссертацию в Московском
госуниверситете им. М.В.Ломоносова по специальности 01.01.06
"Математическая логика, алгебра и теория чисел" и получил степень
кандидата физико-математических наук.
С 2000 года был старшим преподавателем, а с 2001 года - доцентом
кафедры информатики.
В 2004 году присвоено учёное звание доцента по кафедре
информатики.
В 2002-2011 годах исполнял обязанности заместителя декана
факультета прикладной математики и кибернетики по учебной работе и
информатизации.
В 2007 г. защитил докторскую диссертацию в Московском
госуниверситете им. М.В.Ломоносова по специальности 01.01.06
"Математическая логика, алгебра и теория чисел" и получил степень
доктора физико-математических наук.
С 2008 года является профессором кафедры информатики.
С 2009 года - заведующий кафедрой информатики.
С 2020 года - декан факультета прикладной математики и
кибернетики.
Сфера научных интересов
- логическое программирование;
- вычислительная и алгоритмическая сложность;
- теория баз данных;
- теория языков первого порядка.
Основные результаты:
- [1] Исследование сложности параллельности для Хорновского
фрагмента линейной логики. Выделены классы Хорновских секвенций и
установлена сложность задач распознавания принадлежности к этим
классам и сложность задач доказуемости для секвенций из этих
классов.
- [2] Исследование соотношений между вычислительной сложностью и
алгоритмической сложностью множеств. Доказано, что NP-полные по
Тьюрингу проблемы не могут иметь алгоритмическую сложность
распознавания порядка k lg lg n для начальных отрезков длины n
почти для всех n. Доказано, что EXP-полные проблемы имеют
колмогоровскую сложность меньше n - poly(lg n) для начальных
отрезков длины n для бесконечно многих n.
- [3] Исследование сложности построения совершенной модели
пропозициональной нормальной логической программы. Получен ответ на
один из открытых вопросов в работах Айтера и Готтлоба. Построен
класс сложности, для которого эта задача является полной.
- [4-9] Исследование сложности обновления дедуктивных баз данных.
Получены оценки сложности в различных случаях.
- [10-21] Получен трансляционный результат для класса обогащений
арифметики Пресбургера одноместными функциями, согласованными со
сложением. Исследована выразительная сила языков первого порядка
для конечных алгебраических систем, вложенных в случайный граф.
Установлена связь между свойствами псевдоконечной однородности,
изолированности и сводимости. Приведён пример разрешимого
обогащения арифметики пресбургера без свойства коллапса к порядку.
Показана возможность в ряде случаев эффективно транслировать
расширенные формулы в ограниченные.
- [22-33, 37] Исследованы итеративные операторы, их
определённость, разрешимость связанных с ними задач и их
вычислительная сложность. Найдены необходимые и достаточные условия
определённости IFP-операторов. Установлена связь определённости с
категоричностью и сильной минимальностью теории. Установлена
вычислительная сложность логики унарного транзитивного замыкания
для функции следования.
- [34-36, 38-45] Исследованы свойства алгебр языков. Доказана
разрешимость алгебры с объединением, но неразрешимость случая,
когда к объединению добавляется конкатенация или итерация. Далее
результат усилен: неразрешимой оказывается даже алгебра с одной
конкатенацией и односимвольным алфавитом. В качестве обобщений
доказано, что такой же результат имеет место для многосимвольных,
конечных или регулярных языков. В противоположность этому найден
пример алгебры, когда переход к алгебре подмножеств не поднимает, а
опускает сложность теории. Дальнейшие исследования обобщают
результаты о неразрешимости алгебры подмножеств на широкий класс
моноидов и групп. В частности, если брать алгебру конечных
подмножеств, то он верен для произвольных абелевых групп, не
являющихся группами кручения, а также для некоторых абелевых групп
кручения.
- [46] Доказана тривиальность понятий йонсоновского многообразия
и квазимнообразия
Научные публикации:
- Dudakov S.M. The Concurrency Complexity for the Horn
Fragment of Linear Logic // Proc of the fourth Intern.
Simp. LFCS'97. Springer, 1997, 78-87. doi: 10.1007/3-540-63045-7_9
Сложность параллельности для хорновского фрагмента линейной
логики
Как известно, проблема доказуемости в хорновском
фрагменте линейной логики является NP-полной. В данной работе
исследуются различные определения параллельности и устанавливается
сложность доказуемости для соответствующих классов секвенций, а
также сложность распознавания. Вводится понятие k-максимальной
параллельности, сложность доказуемости для соответствующих классов
является полиномиальной по времени. Доказана теорема об иерархии и
установлена сложность распознавания k-максимальной
параллельности.
- Dudakov S.M.On information content of hard sets
// Proc. of intern. conf. on mathematical logic "Maltsev meeting"
(extended abstarct). Novosibirsk, 1999, 79-80.
Информационная сложность полных множеств
Исследуется колмогоровская алгоритмическая сложность NP-
и EXPTIME-полных проблем. Получены два основных результата. Первый
- если P не равно NP, то полиномиально ограниченная колмогоровская
сложность NP-трудных проблем не меньше чем klg(lg(n)). Второй -
обобщение результатов Бука и Лютца на EXPTIME-трудные
множества.
- Dudakov S.M. On the complexity of perfect models of logic
programs // Fundamenta Informaticae, vol. 39(3), 1999 pp.
249-258. doi: 10.3233/FI-1999-39302
Сложность совершенных моделей логических программ
В работе исследуются совершенные модели норамальных
логических программ, устанавливается сложность распознавания
PERF-совместности и PERF-следования. Описана структура совершенных
моделей.
- Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N.
Monotone Expansion of Updates in Logical Databases //
Proc. of 5th International Conference LPNMR'99, Berlin,
Springer-Verlag, 1999 pp. 132-146. doi: 10.1007/3-540-46767-X_10
To find a minimal real change after an update of a
database with integrity constraints (IC) expressed by an extended
logic program is proven to be a hard problem. We define a class of
operators expanding the input updates correctly with respect to the
IC. The particular monotone expansion operator we describe is
incrementally computed in square time. It provides a practical
optimization of the standard complete choice algorithm resolving
the update problem.
- Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Maximal
Expansions of Database Updates // Proc. of FoIKS'2000,
LNCS, 1762, pp.72-87. doi: 10.1007/3-540-46564-2_5
Databases with integrity constraints (IC) are considered.
For each DB update, i.e. a set of facts to add and of facts to
delete, the IC implies its correct expansion: new facts to add and
new facts to delete. Simultaneously, each expanded update induces a
correct simplification of the IC. In the limit this sequence of
expansions and simplifications converges to the maximal correct
update expansion independent from the initial DB state. We show
that such maximal expansion is computed in square time for partial
databases, and that its computation is a coNP-complete problem in
classical databases. However, it is also square time computable in
classical DBs under ICs with some restrictions on the use of
negation. Computing the real change of the initial DB state after
accomplishing an update is a hard problem. The use of maximal
update expansion in the place of initial update can substantially
simplify computation of a new correct DB state.
- Dekhtyar M., Dikovsky A., Dudakov S. On Complexity of
Updates Through Integrity Constraints, // Proc. of the
First Int. Conf. on Computational Logic (CL 2000), LNAI, 1861
(2000), pp. 867-881. doi: 10.1007/3-540-44957-4_58
The computational complexity is explored of finding the
minimal real change of a database after an update constrained by a
logic program. Quite surprisingly, a polynomial time algorithm is
discovered which solves this problem for ground IC in partial
interpretations. Formulated in a "property" form, even under the
premise of fixed database scheme, this problem turns out to be
complete in the first three classes of polynomial hierarchies,
depending on many factors: type of interpretation (total or
partial), presence of variables, use of negation, arity of
predicates, etc. If the database scheme may vary, the complexity
grows exponentially. Meanwhile, we show that under strong
restrictions to negative constraints the problem is solvable in
polynomial time.
- Dudakov S.M. The logic program model updates complexity
(deletion case). // Proceeding of intern. conf. "Logic and
application" (extended abstract). Novosibirsk, 2000.
Сложность обновлений моделей логических программ
(удаления)
We prove that the problem of update of deductive database
can be simplified if only deletions are enabled and additional
formula is an atom. We prove the problem is computable in
polinomial time in propositional case and the problem is
coNP-complete if a logical problem contains
variables.
- Michael I. Dekhtyar, Alexander Ja. Dikovsky, Sergey Dudakov,
Nicolas Spyratos: Maximal state independent approximations to
minimal real change // Annals of Mathematics and Artificial
Intelligence 33(2-4), 2001, pp. 157-204.doi: 10.1023/A:1013112907978
To find a minimal real change after an update of a
database with integrity constraints (IC) expressed in the form of a
generalized logic program, is a hard problem under total
interpretations. Meanwhile, we show that it is solvable in linear
time under partial interpretations. In order to find a practical
solution of this problem under total interpretations, we propose a
method of computing DB state independent correct expansions of
update request and simultaneous optimization of IC with respect to
this expansion. We show that under partial interpretations, optimal
pairs (greatest correct update expansion / simplest equivalent IC)
always exist and can be incrementally computed in square time. From
such pairs we obtain a good approximation to optimal pairs of this
kind under total interpretations. Moreover, we show that such
optimal pairs can be computed under total interpretations as well,
for IC with clauses without negation in the
bodies.
- С.М.Дудаков Сложность обновлений дедуктивных баз данных с
фиксированным ограничением целостности // Вестник ТвГУ.
Серия Прикладная математика, № 1, 2003.
В работе доказано, что если рассматривается случай, когда
ограничения целостности дедуктивной базы данных заданы плоской
логической программой (с переменными) и фиксированы, то сложность
задач обновления полиномиально эквивалентны сложности аналогичных
задач, когда ограниченя не содержат переменных, но не
зафиксированы.
- С.М.Дудаков Трансляционная теорема в предикатных
обогащениях начального фрагмента нестандартных моделей арифметики
Пресбургера // Сложные системы: обработка информации,
моделирование и оптимизация, ТвГУ, Тверь, 2002
Трансляционный результат (трансляционная теорема)
означает, что если взять произвольную модель теории и внедрить в
нее некоторую конечную систему, то любой локально генерический
запрос к внедренной системе с использованием символов теории может
быть переписан без этих символов. В данной работе доказано, что
если взять нестандартную модель арифметики Пресбургера, обогатить
ее произвольными предикатами, определенными на натуральных числах,
то в теории полученной системы выполняется трансляционная
теорема.
- С.М.Дудаков Трансляционный результат для расширений
арифметики Пресбургера одноместной функцией, согласованной со
сложением // Матем. заметки 2004, Т.76, вып. 3, С.362-371.
doi: 10.1023/B:MATN.0000043461.68759.1d
Доказано, что если обогатить арифметику Пресбургера
произвольной одноместной функцией, согласованной со сложением,
например, экспонентой или факториалом, то в полученной теории
выполняется трансляционная теорема.
- С.М.Дудаков Трансляционная теорема для теорий I-сводимых
алгебраических систем // Известия РАН, сер. математическая
2004, Т.68, №5, С.67-90. doi: 10.1070/IM2004v068n05ABEH000503
Показано, что отсутствие независимой формулы в теории не
является необходимым условием для I-сводимости её моделей даже для
расширений арифметики Пресбургера. Доказано, что из I-сводимости
малой алгебраической системы автоматически следует, что каждая
формула эквивалентна в ней некоторой P-ограниченной формуле,
следовательно, для теорий таких систем выполняется трансляционная
теорема.
- С.М.Дудаков Выразительная сила языков запросов первого
порядка для баз данных на неупорядоченном случайном графе
// Вестник НовГУ, Серия технические науки, №34, 2005. С.51-57
Исследуется вопрос, расширяется ли множество выразимых в
логике первого порядка запросов, если элементы базы данных берутся
из неупорядоченного случайного графа.
- С.М.Дудаков Разрешимая теория без трансляционной
теоремы // Вестник ТвГУ. Серия Прикладная математика, №
6(12), 2005. С.23-26
Предлагается пример теории, который опровергает гипотезу
о том, что не существует разрешимых теорий без транансляционной
теоремы.
- С.М.Дудаков, М.А.Тайцлин Трансляционный результат для
языков запросов в теории баз данных // Успехи
математических наук, №61:2(368), 2006, С.2-65 doi: 10.4213/rm1713
В центре нашего внимания так называемые относительные
свойства изолированности и псевдоконечной однородности и универсумы
без независимой формулы. Для сводимых теорий мы доказываем теорему
об ограниченности. Для сводимых и ограниченных теорий мы доказываем
теорему об относительной изолированности и, как следствие, получаем
для сводимых теорий трансляционную теорему. Мы также замечаем, что
сводимость равносильна относительной изолированности. С другой
стороны, мы приводим теоремы, которые показывают, что для
эффективно сводимых теорий, в которых существует эффективная почти
неразличимая последовательность, возможна эффективная трансляция
локально генерических запросов, использующих, кроме упорядочения и
имён хранящихся таблиц, также и отношения и операции универсума, в
запросы, которые эти отношения и операции универсума уже не
используют. Мы приводим также пример такого обогащения арифметики
Пресбургера, что для этого обогащения трансляционная теорема не
имеет места, но элементарная теория этого обогащения разрешима. Это
дает отрицательный ответ на некоторые открытые
вопросы.
- S.M.Dudakov Isolation and reducibility properties and the
collapse result // Proc. of intern.conf. CSR-2006. LNCS
3967, Springer, 2006. С.171-177. doi: 10.1007/11753728_19
Two methods are used usually for to establish the
collapse result for theories. They use the isolation property and
the reducibility property. Early it is shown that the reducibility
implies the isolation. We prove that these methods are
equivalent.
- С.М.Дудаков Трансляционная теорема и автоматные
структуры // Вестник ТвГУ, серия Прикладная математика,
№4(21), 2006. С.5--35.
Предлагается пример запроса к базе данных, который
является локально генерическим и может быть записан с
использованием отношений автоматных систем, но не может быть
записан ограниченной формулой. Тем самым опровергаются гипотезы о
том, что в автоматных структурах соблюдается трансляционная
теорема, о том, что не существует разрешимых обогащений теории
дискретного линейного порядка без трансляционной теоремы, и что в
каждом таком обогащении без трансляционной теоремы существует
формула, способная выделить любое подмножество любого конечного
множества. Это построение так же опровергает две более слабые
гипотезы, утверждающие то же самое для расширений арифметики
Пресбургера. Кроме того, далее мы строим теории, опровергающие одну
из гипотез из работы Болдвина и Бенедикта.
- С.М.Дудаков Псевдоконечная однородность, изолированность
и сводимость // Матем. заметки, Т.81, вып. 4, 2004,
С.515-527. doi: 10.1134/S0001434607030224
Ранее установлено (Дудаков С.М., Тайцлин М.А.), что из
сводимости некоторых моделей теории следует второе свойство
псевдоконечной однородности для этой теории. Здесь мы доказываем
обратное: из любого (первого или второго) свойства псевдоконечной
однородности теории следует сводимость некоторых ее моделей, и,
следовательно, второе свойство изолированности. Это доказывает
также эквивалентность вторых свойств изолированности и
псевдоконечной однородности, что контрастирует с тем, что первое
свойство псевдоконечной однородности является более общим, чем
первое свойство изолированности (Белеградек О.В., Столбоушин А.П.,
Тайцлин М.А.).
- С.М.Дудаков Достаточные условия эффективной трансляции
локально генерических запросов, // Фундаментальная и
прикладная математика. 2009. Т. 15. № 5. С. 49-61.
Данная работа является продолжением исследований по
теории языков запросов первого порядка к базам данных. Ранее было
установлено, что во многих разрешимых теориях имеет место
трансляционная теорема: каждый локально генерический запрос
эквивалентен некоторому ограниченному, но вопрос о возможности
эффективного нахождения этого запроса почти не исследовался.
Используя полученные автором ранее результаты, мы предлагаем метод
эффективного нахождения этих запросов для широкого класса теорий,
который включает арифметику Пресбургера и теорию действительных
чисел.
- С.М.Дудаков МОНАДИЧЕСКИЕ СОСТОЯНИЯ НАД УПОРЯДОЧЕННЫМ
УНИВЕРСАЛЬНЫМ СЛУЧАЙНЫМ ГРАФОМ И КОНЕЧНЫЕ АВТОМАТЫ //
Известия Российской академии наук. Серия математическая. 2011. Т.
75. № 5. С. 47-64. doi: 10.4213/im4077
В работе продолжено изучение выразительной силы языка
логики предикатов для конечных алгебраических систем, вложенных в
бесконечные, которое было начато в работах М.А.Тайцлина,
М.Бенедикта, Л.Либкина и др. Изучено, какие свойства конечной
монадической системы можно выразить с помощью формул, если вложить
такую систему в линейно упорядоченный произвольным образом
случайный граф. В работе используется представление Бюхи для связи
монадических состояний и формальных языков. Показано, что если
ограничиться рассмотрением только инвариантных в линейно
упорядоченных случайных графах формул, то такие формулы
соответствуют конечным автоматам. Продемонстрировано, что
$=$-инвариантные формулы, выражающие собственные свойства вложенных
систем, способны выразить только булеву комбинацию свойств вида
"мощность пересечения одноместных предикатов принадлежит одной из
конечного числа фиксированных конечных или бесконечных
арифметических прогрессий."
- Dudakov S.M. SUFFICIENT CONDITIONS FOR EFFECTIVE
TRANSLATION OF LOCALLY GENERIC QUERIES // Journal of
Mathematical Sciences. 2011. Т. 172. № 5. С. 654-662. doi: 10.1007/s10958-011-0211-3
This paper continues investigations into the database of
queries of first-order language theory. It is known that for many
decidable theories, the collapse result holds: each locally generic
query is equivalent to some restricted query. But, until now, the
problem of effective construction of this query remains almost
unexplored. We use earlier results of the author on the
construction of a method of effective obtaining this query. The
method is rather general and applicable, for example, to the
Presburger arithmetic and the real number theory.
- С.М.Дудаков О БЕЗОПАСНОСТИ РЕКУРСИВНЫХ ЗАПРОСОВ
// Вестник Тверского государственного университета. Серия:
Прикладная математика. 2012. № 4 (27). С. 71-80.
В работе исследуется вопрос об определенности рекурсивных
запросов на универсуме. В качестве модели рекурсивного запроса
применяется оператор инфляционной фиксированной точки IFP.
Исследованы основные свойства IFP-оператора и показано, что модели
счетно-категоричных теорий являются безопасными.
- С.М.Дудаков О БЕЗОПАСНОСТИ IFP-ОПЕРАТОРОВ И РЕКУРСИВНЫХ
ЗАПРОСОВ // Вестник Тверского государственного
университета. Серия: Прикладная математика. 2013. № 2 (29). С.
5-13.
В работе продолжается исследование об определенности
рекурсивных запросов на универсуме. Ранее нами показано, что модели
счетно-категоричных теорий безопасны. В данной работе мы
показываем, что счетная категоричность необходимым условием не
является, и предлагаем необходимые и достаточные условия
безопасности IFP-оператора.
- С.М.Дудаков НЕРАЗРЕШИМОСТЬ ПРОБЛЕМЫ ОПРЕДЕЛЕННОСТИ
БИНАРНЫХ IFP-ОПЕРАТОРОВ ДЛЯ ТЕОРИИ ОДНОГО СЛЕДОВАНИЯ //
Вестник Тверского государственного университета. Серия: Прикладная
математика. 2014. № 4. С. 7-15.
В работе продолжается исследование определенности
оператора инфляционной фиксированной точки. Показано, что проблема
определенности бинарного IFP-оператора для теории следования
алгоритмически неразрешима.
- С.М.Дудаков СИЛЬНАЯ МИНИМАЛЬНОСТЬ И
IFP-БЕЗОПАСНОСТЬ // Вестник Тверского государственного
университета. Серия: Прикладная математика. 2015. № 3. С. 25-32.
В работе продолжено исследование IFP-безопасности теорий.
Доказано, что среди полных конечно аксиоматизируемых сильно
минимальных теорий IFP-безопасных нет.
- Dudakov S.M. ON INFLATIONARY FIX-POINT OPERATORS
SAFETY // Lobachevskii Journal of Mathematics. 2015. Т. 36.
№ 4. С. 328-331. doi: 10.1134/S1995080215040022
We continue to investigate a safety of recursive queries
(inflationary fix-point operators) over infinite universes. In the
previous paper we have proved that models of countable categorical
theories are safe. In this paper we propose a necessary and
sufficient condition for IFP-safety and obtain a solution of the
problem for linear order theories.
- С.М.Дудаков О выразительной силе логики одноместного
транзитивного замыкания для дискретного порядка // Вестник
Тверского государственного университета. Серия: Прикладная
математика. 2017. № 4. С. 25-33. doi: 10.26456/vtpmk186
В работе показано, что в теории дискретного линейного
порядка с одноместным оператором транзитивного замыкания с помощью
формул длины n можно представить сложение, умножение и экспоненту
для натуральных чисел вплоть до H2(n), где H2(n) -
гиперэкспонента.
- С.М.Дудаков О сложности разрешения теории следования с
унарным оператором транзитивного замыкания // "Актуальные
проблемы прикладной математики, информатики и механики" сборник
трудов Международной научно-технической конференции. Воронежский
государственный университет, 2017 Воронеж:
"Научно-исследовательские публикации"; Общество с ограниченной
ответственностью "Вэлборн", 2017. С.1503-1507.
Доказано, что в теории следования с унарным оператором
транзитивного замыкания для любого разрешающего алгоритма найдётся
бесконечно много формул f, на которых он будет работать не менее
H2(O(n)) шагов. Здесь n - длина формулы f, H2 - функция
гиперэкспоненты по основанию 2.
- С.М.Дудаков Использование итеративных операторов в
классических логических теориях // "Алгебра и теория
алгоритмов" Сборник материалов Всероссийской конференции,
посвящённой 100-летию факультета математики и компьютерных наук
Ивановского государственного университета. Иваново : Ивановский
государственный университет, 2018. С.145-147
Мы показываем связь конечности IFP-операторов с
разрешимостью IFP-теории.
- С.М.Дудаков On safety of unary and non-unary inflationary
fixed point operators // 9TH WORKSHOP PSSV proceedings.
Ярославль : Ярославский государственный университет им. П.Г.
Демидова, 2018. С.45-50.
We investigate unary inflationary fixed point (IFP)
operators and establish some differences between the unary
IFP-operators and general ones.
- С.М.Дудаков О безопасности одно и многоместных
IFP-операторов // Моделирование и анализ информационных
систем. 2018. Т. 25. № 5 (77). С. 525-533. doi: 10.18255/1818-1015-2018-5-525-533
В работе изучается безопасность унарных операторов
инфляционной неподвижной точки (IFP-операторов), то есть
возможность их вычисления за конечное время. Такие операторы в
точности соответствуют рекурсивным SQL-запросам, поэтому изучаемый
вопрос имеет непосредственное отношение к базам данных. Исследуемая
проблема возникает из-за того, что при одновременном применении в
SQL запросе рекурсии и отношений универсума, например, сложения,
может оказаться так, что процедура вычисления результата запроса
зациклится. Более того, такая комбинация позволяет моделировать
работу универсального вычислительного устройства, например, машины
Тьюринга, поэтому вопрос о возможности вычисления SQL запроса за
конечное время оказывается алгоритмически неразрешимым. В
предыдущих работах были введены и изучены некоторые свойства
универсумов, которые позволяют гарантировать возможность вычисления
любых запросов за конечное время. Здесь мы изучаем вопрос о том,
насколько существенна местность IFP-операторов в контексте их
безопасности. Основным результатом настоящей работы является
демонстрация того, что если ограничиться только унарными
IFP-операторами, то не имеют места результаты, справедливые для
IFP-операторов в общем случае без ограничения местности. Построен
пример универсума, в котором все унарные IFP-операторы, не
вложенные один в другой, безопасны. Вместе с тем в этом универсуме
существуют небезопасные бинарные IFP-операторы, таким образом, при
изменении местности безопасность может утрачиваться. Кроме того,
существуют и небезопасные вложенные один в другой унарные
операторы. Это контрастирует с общим случаем, в котором такое
невозможно. Также существуют элементарно эквивалентные универсумы,
в которых те же самые унарные IFP-операторы безопасными не
являются. Такое поведение тоже отличается от поведения
IFP-операторов произвольной местности.
- С.М.Дудаков О границах трансфинитного построения
инфляционной неподвижной точки // Вестник Тверского
государственного университета. Серия: Прикладная математика. 2018.
№ 3. С. 72-80. doi: 10.26456/vtpmk510
В работе показано, что если универсум допускает
существование оператора инфляционной неподвижной точки, который не
вычисляется за конечное число шагов, то существуют операторы
инфляционной неподвижной точки, требующие для своего трансфинитного
построения произвольного числа шагов вплоть до ординала
$\omega^\omega$ в любом универсуме. Для дискретного порядка
продемонстрирована возможность построения за произвольное число
шагов.
- С.М.Дудаков On computational complexity of successor
theory with unary transitive closure // IOP Conf. Series:
Journal of Physics: Conf. Series 1202 (2019). doi: 10.1088/1742-6596/1202/1/012018
The present article concerns the theory of the successor
function with the unary transitive closure (TC) operator. This
theory is equivalent to the TC-theory of discrete linear order with
respect to TC-definability. We prove that any decision algorithm
for this theory has at least hyperexponential computational
complexity. The latter is much higher than the complexity of the
same theories without the TC-operator.
- Dudakov S.M., Karlov B.N. On Decidability of Regular
Languages Theories // Computer Science – Theory and
Applications, Novosibirsk, 2019, Springer, LNCS 11532, pp.119-130.
DOI: 10.1007/978-3-030-19955-5_11
This paper is dedicated to studying decidability
properties of some regular languages theories. We prove that the
regular languages theory with the Kleene star only is decidable. If
we use union and concatenation simultaneously then the theory
becomes both $\Sigma_1$- and $\Pi_1$-hard over the one-symbol
alphabet. Finally, we prove that the regular languages theory over
one-symbol alphabet with union and the Kleene star is equivalent to
arithmetic. The Kleene star is definable with union and
concatenation, hence, the previous theory is equivalent to
arithmetic also.
- С.М. Дудаков Об алгоритмических свойствах алгебры
конечных подмножеств некоторых уноидов // Вестник Тверского
государственного университета. Серия: Прикладная математика. 2019.
№ 4. С. 108-116. DOI: 10.26456/vtpmk550
В работе показано, что если рассмотреть алгебру из
некоторых уноидов в виде "кустов", соединённых в бесконечную линию,
и построить алгебру её конечных подмножеств, то полученная система
имеет теорию, допускающую эффективную элиминацию кванторов
независимо от исходной. Таким образом, показано, что теория алгебры
конечных подмножеств может быть существенно проще алгоритмически,
чем теория исходной, а операция объединения для алгебр подмножеств
является существенной для алгоритмических свойств.
- С.М. Дудаков О неразрешимости алгебры односимвольных
языков с операцией конкатенации // Материалы конференции
"Алгебра и математическая логика: теория и приложения". Казань:
Изд-во КФУ, 2019. С.101-103.
Как известно, теория языка всех слов с операцией
конкатенации неразрешима при наличии хотя бы двух символов
(Гжегорчик, 2000). Для односимвольного алфавита соответствующая
алгебра изоморфна аддитивному моноиду натуральных чисел, поэтому
имеет разрешимую теорию. Возникает вопрос: что можно сказать о
теории, в которой классические словарные операции, например,
конкатенация, применяются не к отдельным словам, а к целым языкам.
В качестве носителя в этом случае выступает какое-либо множество
языков, обладающее необходимыми свойствами замкнутости. Одним из
наиболее "естественных" является класс автоматных языков, который
замкнут относительного очень многих действий (Хопкрофт, 2013). В
работе (Дудаков, Карлов, 2019) показано, что если сигнатура
включает в себя объединение, а также ещё хотя бы одну из операций:
конкатенацию или итерацию, то теория множества автоматных языков
будет неразрешимой даже для однобуквенного алфавита. Более того,
продемонстрировано, что степень неразрешимости такой теории
эквивалентна полной элементарной арифметике. Мы усиливаем этот
результат, доказывая, что одной операции конкатенации языков
достаточно, чтобы такая теория класса регулярных языков была
алгоритмически эквивалентна полной элементарной
арифметике.
- С.М. Дудаков On Safety of Unary and Nonunary IFP
Operators // Automatic Control and Computer Sciences, 2019,
Vol. 53, No. 7, pp. 683–688. DOI: 10.3103/S0146411619070034
The article investigates the safety of unary inflationary
fixed point operators (IFP-operators), i.e., their computability in
finitely many steps. Such operators correspond exactly to recursive
SQL queries. Therefore, the problem under investigation is directly
related to database theory. The problem arises from the fact that
if recursion and universe relations, e.g., addition, are
simultaneously used in a SQL query, then a query evaluation can
fall into an infinite loop. Moreover, such a combination makes it
possible to model a universal computing device, e.g., a Turing
machine. Hence, the problem of finite computability for such SQL
queries is undecidable. In our previous works, we established some
properties of a universe those guarantee the finite computability
of any IFP-operator in the universe. In this article, we
investigate a connection between an arity of IFP-operators and
their safety. The main result of this article is that some results
for general IFP-operators do not hold for unary ones. An instance
of a universe is constructed in which all unnested unary
IFP-operators are safe. However, there are unsafe binary
IFP-operators in this universe. Therefore, IFP-operators can become
unsafe if the arity changes. In addition, there are unsafe nested
unary operators. This contrasts with the general case in which this
is impossible. There are also elementary equivalent universes where
the same unary IFP-operators are unsafe. This behavior is also
different from the behavior of general
IFP-operators.
- С.М. Дудаков On Undecidability of Concatenation Theory
for One-Symbol Languages // Lobachevskii Journal of
Mathematics, 2020, Vol. 41, No. 2, pp. 168–175. DOI: 10.1134/S1995080220020055
We investigate concatenation theories for some sets of
one-symbol languages. These sets can be the set of all languages,
the set of regular languages, or the set of finite languages. We
prove that all such theories are undecidable. The last two theories
are algorithmically equivalent to elementary arithmetic. The first
is equivalent to second order arithmetic.
- Dudakov S.M., Karlov B.N. On Decidability of Regular
Languages Theories //Theory of Computing Systems, 2020.
DOI: 10.1007/s00224-020-09995-4
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.
- С.М.Дудаков. Об определимости в алгебре конечных языков с
конкатенацией множества односимвольных языков // Вестник
Тверского государственного университета. Серия: Прикладная
математика. 2020. № 4. С. 5-13. DOI: 10.26456/vtpmk601
Мы рассматриваем алгебру всех конечных языков над
многосимвольным алфавитом с операцией конкатенации. Ранее было
показано, что если взять подобную алгебру, но состоящую из всех
регулярных многосимвольных языков, то в ней можно интерпретировать
алгебру регулярных односимвольных языков, откуда следует, что
теория обеих этих алгебр эквивалентна элементарной арифметике. В
настоящей работе мы доказываем аналогичный результат для алгебры
конечных языков: в ней определима подалгебра односимвольных языков,
а сама она имеет теорию алгоритмически эквивалентную элементарной
арифметике.
- С.М.Дудаков. Об алгоритмической неразрешимости теории
конечных подмножеств некоторых моноидов // Актуальные
проблемы прикладной математики, информатики и механики : сборник
трудов МеждуА43 народной научной конференции, Воронеж, 7–9 декабря
2020 г. – Воронеж : Издательство «Научно-исследовательские
публикации», 2021. – С. 1602-1607. - ISBN 978-5-6045486-1-5
Мы рассматриваем произвольные коммутативные моноиды с
сокращением, содержащие элементы бесконечного порядка. На них мы
обобщаем результат полученный нами ранее для циклического моноида:
конечные подмножества в таких моноидах сами образуют моноид, в
котором интерпретируется элементарная арифметика. Следовательно,
теория конечных подмножеств таких моноидов неразрешима.
- S.M.Dudakov On Undecidability of Subset Theory for Some
Monoids // Journal of Physics: Conference Series. 2021.
1902, 012060. DOI: 10.1088/1742-6596/1902/1/012060
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 H with an
element of infinite order, and generalize the previous claims to
the corresponding monoid exp H.
- С.М.Дудаков. О теории моноида конечных подмножеств для
одной абелевой группы кручения // Вестник Тверского
государственного университета. Серия: Прикладная математика. 2021.
№ 2. С. 39-55. DOI: 10.26456/vtpmk615
Ранее был доказан следующий результат: если абелева группа G не
является группой кручения, то теория моноида ее конечных
подмножеств позволяет интерпретировать элементарную арифметику. В
настоящей работе мы приводим пример, который показывает, что
аналогичный результат можно получить и, по крайней мере, для
некоторых групп кручения.
- S.M.Dudakov. On Undecidability of Finite Subsets Theory
for Torsion Abelian Groups // Mathematics, 2022, Vol. 10, №
3, P.533. DOI: 10.3390/math10030533
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. In this paper we prove the given
theorem for Abelian torsion groups that have elements of unbounded
order: for such group, the theory of finite subsets allows
interpreting the elementary arithmetic.
- С.М.Дудаков. О конечных фигурах в линейных пространствах
над полями конечной характеристики // Актуальные проблемы
прикладной математики, информатики и механики : Сборник трудов
Международной научной конференции, Воронеж, 13–15 декабря 2021
года. – Воронеж: Общество с ограниченной ответственностью
"Вэлборн", 2022. – С. 1564-1570. EDN: DOVLIJ
В работе изучаются алгебры, которые построены из линейных
пространств над полями конечной характеристики с помощью перехода к
алгебре конечных подмножеств. Доказывается, что при одновременном
использовании для фигур поэлементного сложения и
теоретико-множественных действий появляется возможность
интерпретации элементарной арифметики. Далее этот результат
применяется для того, чтобы показать аналогичную возможность
интерпретации арифметики при рассмотрении конечных подмножеств
бесконечных абелевых групп конечной экспоненты.
- С.М.Дудаков. О йонсоновских многообразиях и
квазимногообразиях // Вестник ТвГУ. Серия: Прикладная
математика. 2022. № 4. С. 5-10. DOI: 10.26456/vtpmk650
В работах некоторых авторов было введено понятие йонсоновского
многообразия и квазимногообразия и для таких классов алгебраических
систем доказаны разного рода утверждения. Мы показываем, что на
самом деле йонсоновские многообразия и квазимногообразия
ограничиваются всего лишь классами множеств и либо пунктированных
множеств в зависимости от сигнатуры. Таким образом, результаты,
полученные в упомянутых выше работах другими исследователями,
является тривиальными.
Научно-методические публикации:
- С.М.Дудаков. Информатика. // Фонд контрольных заданий для
квалификационной аттестации студентов факультета ПМиК ТвГУ по
основам фундаментальных и компьютерных знаний: Учебно-методический
сборник. Тверь: ТвГУ. 2002. (Рекомендовано УМО в качестве
учебного пособия для студентов специальности "Прикладная математика
и информатика")
- С.М.Дудаков. Математическое введение в информатику: Учебное
пособие. Тверь: ТвГУ. 2003. - 240c. (Рекомендовано УМО в
качестве учебного пособия для студентов специальности "Прикладная
математика и информатика")
- С.М.Дудаков. Информатика. // Фонд контрольных заданий для
квалификационной аттестации студентов факультета ПМиК ТвГУ по
основам фундаментальных и компьютерных знаний: Учебно-методический
сборник. Тверь: ТвГУ. 2007. (Рекомендовано УМО в качестве
учебного пособия для студентов специальности "Прикладная математика
и информатика")
- С.М.Дудаков. Языки программирования и методы трансляции. //
Фонд контрольных заданий для квалификационной аттестации студентов
факультета ПМиК ТвГУ по основам фундаментальных и компьютерных
знаний: Учебно-методический сборник. Тверь: ТвГУ. 2007.
(Рекомендовано УМО в качестве учебного пособия для студентов
специальности "Прикладная математика и информатика")
- С.М.Дудаков. Основы теории моделей: Учебник. Тверь: ТвГУ. 2013.
- 480c.
- Захарова И.В., Дудаков С.М., Язенин А.В., Солдатенко И.С.
О методических аспектах разработки примерных образовательных
программ высшего образования // Образовательные технологии
и общество. 2015. Т. 18. № 3. С. 330-354.
- Захарова И.В., Дудаков С.М., Язенин А.В. О разработке
примерного учебного плана по УГСН «Компьютерные и информационные
науки» в соответствии с профессиональными стандартами //
Вестник Тверского государственного университета. Серия: Педагогика
и психология. 2016. № 2. С. 84-100. 13
- Захарова И.В., Дудаков С.М., Язенин А.В. О разработке
магистерской программы по УГСН «Компьютерные и информационные
науки» в соответствии с профессиональными стандартами //
Вестник Тверского государственного университета. Серия: Педагогика
и психология. 2016. № 3. С. 114-126.
- Захарова И.В., Дудаков С.М., Солдатенко И.С.
Проектирование образовательных программ в области икт с
учётом профессиональных стандартов // Инженерное
образование. 2017. № 21. С. 140-144.
- Дудаков С.М., Захарова И.В. Мониторинг сформированности
математических компетенций у студентов it-специальностей //
Инженерное образование. 2017. № 21. С. 90-95.
- Захарова И.В., Дудаков С.М. Сравнительный анализ
образовательных стандартов ФГОС ВО 3+ и ФГОС ВО 3++ по направлению
подготовки "Прикладная математика и информатика" //
Образовательные технологии и общество, 2019, 22(4), с.96-105.
- С.М.Дудаков, Б.Н.Карлов. Математическое введение в информатику
: учебник по дисциплине «Теоретические основы информатики» 2-е
издание, исправленное и дополненное. Тверь: ТвГУ. 2017. -
320c.
- Дехтярь М.И. Лекции по дискретной математике [Электронный
ресурс] : учебник / Дехтярь М.И., Дудаков С.М., Карлов Б.Н. - Изд.
2-е, перераб. и доп. - Тверь : Тверской государственный
университет, 2019. - 512с.
- С.М.Дудаков. Универсальная алгебра : учебное пособие. Тверь:
ТвГУ. 2019. - 112c.
- Дудаков С.М. Математическое введение в информатику : учебник по
дисциплине "Теоретические основы информатики" / С. М. Дудаков, Б.
Н. Карлов. - Изд. 3-е, испр. и доп. - Тверь : Тверской
государственный университет, 2020. - 320с.
- Дехтярь М.И. Сборник задач по множествам, булевым функциям и
математической логике : учебное пособие / М. И. Дехтярь, С. М.
Дудаков, Б. Н. Карлов. - Тверь : Тверской государственный
университет, 2020. - 128с.
- Дехтярь М. И. Лекции по дискретной
математике : Учебник / М. И. Дехтярь, С. М. Дудаков, Б. Н.
Карлов. – 3-е издание, исправленное и дополненное. – Тверь :
Тверской государственный университет, 2021. – 528 с.
- Дехтярь М. И. Задачник по дискретной
математике : учебное пособие / М. И. Дехтярь, С. М. Дудаков, Б.
Н. Карлов. – 2-е издание, переработанное и дополненное. – Тверь :
Тверской государственный университет, 2021. – 368 с.
Читаемые курсы
- Дискретная математика
- Математическая логика и теория алгоритмов
- Общая алгебра
- Прикладная алгебра и теория чисел
- История и методология математики и информатики
Ученики, имеющие ученую степень
- Снятков Алексей Сергеевич, кандидат физико-математических наук,
Ярославский государственный университет им.Демидова, 2012
- Золотов Александр Сергеевич, кандидат физико-математических
наук, Приволжский (Казанский) федеральный университет, 2017