Окончил Тверской госуниверситет по специальности "Прикладная математика", получил квалификацию "Математик".

После окончания Тверского госуниверситета в 1997-2000 годах работал в университете ассистентом кафедры информатики.

В 2000 г. защитил кандидатскую диссертацию в Московском госуниверситете им. М.В.Ломоносова по специальности 01.01.06 "Математическая логика, алгебра и теория чисел" и получил степень кандидата физико-математических наук.

С 2000 года был старшим преподавателем, а с 2001 года - доцентом кафедры информатики.

В 2004 году присвоено учёное звание доцента по кафедре информатики.

В 2002-2011 годах исполнял обязанности заместителя декана факультета прикладной математики и кибернетики по учебной работе и информатизации.

В 2007 г. защитил докторскую диссертацию в Московском госуниверситете им. М.В.Ломоносова по специальности 01.01.06 "Математическая логика, алгебра и теория чисел" и получил степень доктора физико-математических наук.

С 2008 года является профессором кафедры информатики.

С 2009 года - заведующий кафедрой информатики.

С 2020 года - декан факультета прикладной математики и кибернетики.

В 2025 году присвоено учёное звание профессора по специальности 1.1.5 "Математическая логика, алгебра, теория чисел и дискретная математика".

Сфера научных интересов

• логическое программирование;
• вычислительная и алгоритмическая сложность;
• теория баз данных;
• теория языков первого порядка.

Основные результаты:

• [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-53, 55, 58] Исследованы свойства алгебр языков. Доказана разрешимость алгебры с объединением, но неразрешимость случая, когда к объединению добавляется конкатенация или итерация. Далее результат усилен: неразрешимой оказывается даже алгебра с одной конкатенацией и односимвольным алфавитом. В качестве обобщений доказано, что такой же результат имеет место для многосимвольных, конечных или регулярных языков. В противоположность этому найден пример алгебры, когда переход к алгебре подмножеств не поднимает, а опускает сложность теории. Дальнейшие исследования обобщают результаты о неразрешимости алгебры подмножеств на широкий класс моноидов и групп. Полностью решена эта проблема в случае бесконечных абелевых групп: для любой абелевой группы алгебра её конечных подмножеств допускает интерпретацию элементарной арифметики. Дальнейшим шагом стало изучение классов алгебр подмножеств. Установлено, что для широкого класса алгебр (линейных пространств, абелевых групп, произвольных групп, моноидов, полугрупп, всевозможных группоидов) соответствующий класс алгебр подмножеств допускает интерпретацию элементарной арифметики, поэтому неразрешим и не рекурсивно аксиоматизируем. Далее изучены решётки подалгебр и для них доказан аналогичный результат: для классов линейных пространств, абелевых групп, произвольных групп, моноидов, полугрупп соответствующий класс решёток подалгебр допускает интерпретацию элементарной арифметики, неразрешим и не рекурсивно аксиоматизируем. Для класса конечных линейных пространств показано, что аналогичные классы имеют Π₁-полную теорию. Для множества всех фигур, не только конечных, в бесконечных линейных пространствах установлен результат об эквивалентности такой теории арифметике второго порядка. Далее были усоврешенствованы методы интерпретации, что позволило проинтерпретировать элементарную арифметику в решётке подгруппоидов, которые необязательно ассоциативны. Если ограничиться не только конечными, но и счётно бесконечными подгруппоидами, то найдена и верхняя оценка: такая теория интерпретируется в арифметике второго порядка.
• [46] Доказана тривиальность понятий йонсоновского многообразия и квазимнообразия
• [54, 56-57, 59] Исследованы различные обобщения вывода в формальных грамматиках и установлена сложность задач, с ними связанных. Основные идеи: ограничения на количества применений правил вывода и количества нетерминальных символов, которые в выводах применяются. Продемонстрировано, что для тотальных выводов, когда требуется чтобы каждое правило было применено не менее одного раза задача выводимости в КС-грамматике будет NP-полной даже для пустого слова. Для нескоращающих грамматик, этот результат верен для непустых слов. Аналогичные результаты имеют место, когда требует каждый нетерминал применять хотя бы раз. При верхнем ограничении: каждое правило используется не более чем единожды - задача выводимости в КС-грамматиках будет NP-полной в общем случае для пустого слова, но полиномиально разрешима, если заранее ограничить количество нетерминалов. Для произвольных слов эта задача будет полиномиально разрешимой только в случае, когда грамматика содержит один терминал и один нетрминал, а при большем их количестве - снова будет NP-полной.

Научные публикации:

1. 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-максимальной параллельности.
2. 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-трудные множества.
3. 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-следования. Описана структура совершенных моделей.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. С.М.Дудаков Сложность обновлений дедуктивных баз данных с фиксированным ограничением целостности // Вестник ТвГУ. Серия Прикладная математика, № 1, 2003.
   В работе доказано, что если рассматривается случай, когда ограничения целостности дедуктивной базы данных заданы плоской логической программой (с переменными) и фиксированы, то сложность задач обновления полиномиально эквивалентны сложности аналогичных задач, когда ограниченя не содержат переменных, но не зафиксированы.
10. С.М.Дудаков Трансляционная теорема в предикатных обогащениях начального фрагмента нестандартных моделей арифметики Пресбургера // Сложные системы: обработка информации, моделирование и оптимизация, ТвГУ, Тверь, 2002
    Трансляционный результат (трансляционная теорема) означает, что если взять произвольную модель теории и внедрить в нее некоторую конечную систему, то любой локально генерический запрос к внедренной системе с использованием символов теории может быть переписан без этих символов. В данной работе доказано, что если взять нестандартную модель арифметики Пресбургера, обогатить ее произвольными предикатами, определенными на натуральных числах, то в теории полученной системы выполняется трансляционная теорема.
11. С.М.Дудаков Трансляционный результат для расширений арифметики Пресбургера одноместной функцией, согласованной со сложением // Матем. заметки 2004, Т.76, вып. 3, С.362-371. doi: 10.1023/B:MATN.0000043461.68759.1d
    Доказано, что если обогатить арифметику Пресбургера произвольной одноместной функцией, согласованной со сложением, например, экспонентой или факториалом, то в полученной теории выполняется трансляционная теорема.
12. С.М.Дудаков Трансляционная теорема для теорий I-сводимых алгебраических систем // Известия РАН, сер. математическая 2004, Т.68, №5, С.67-90. doi: 10.1070/IM2004v068n05ABEH000503
    Показано, что отсутствие независимой формулы в теории не является необходимым условием для I-сводимости её моделей даже для расширений арифметики Пресбургера. Доказано, что из I-сводимости малой алгебраической системы автоматически следует, что каждая формула эквивалентна в ней некоторой P-ограниченной формуле, следовательно, для теорий таких систем выполняется трансляционная теорема.
13. С.М.Дудаков Выразительная сила языков запросов первого порядка для баз данных на неупорядоченном случайном графе // Вестник НовГУ, Серия технические науки, №34, 2005. С.51-57
    Исследуется вопрос, расширяется ли множество выразимых в логике первого порядка запросов, если элементы базы данных берутся из неупорядоченного случайного графа.
14. С.М.Дудаков Разрешимая теория без трансляционной теоремы // Вестник ТвГУ. Серия Прикладная математика, № 6(12), 2005. С.23-26
    Предлагается пример теории, который опровергает гипотезу о том, что не существует разрешимых теорий без транансляционной теоремы.
15. С.М.Дудаков, М.А.Тайцлин Трансляционный результат для языков запросов в теории баз данных // Успехи математических наук, №61:2(368), 2006, С.2-65 doi: 10.4213/rm1713
    В центре нашего внимания так называемые относительные свойства изолированности и псевдоконечной однородности и универсумы без независимой формулы. Для сводимых теорий мы доказываем теорему об ограниченности. Для сводимых и ограниченных теорий мы доказываем теорему об относительной изолированности и, как следствие, получаем для сводимых теорий трансляционную теорему. Мы также замечаем, что сводимость равносильна относительной изолированности. С другой стороны, мы приводим теоремы, которые показывают, что для эффективно сводимых теорий, в которых существует эффективная почти неразличимая последовательность, возможна эффективная трансляция локально генерических запросов, использующих, кроме упорядочения и имён хранящихся таблиц, также и отношения и операции универсума, в запросы, которые эти отношения и операции универсума уже не используют. Мы приводим также пример такого обогащения арифметики Пресбургера, что для этого обогащения трансляционная теорема не имеет места, но элементарная теория этого обогащения разрешима. Это дает отрицательный ответ на некоторые открытые вопросы.
16. 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.
17. С.М.Дудаков Трансляционная теорема и автоматные структуры // Вестник ТвГУ, серия Прикладная математика, №4(21), 2006. С.5--35.
    Предлагается пример запроса к базе данных, который является локально генерическим и может быть записан с использованием отношений автоматных систем, но не может быть записан ограниченной формулой. Тем самым опровергаются гипотезы о том, что в автоматных структурах соблюдается трансляционная теорема, о том, что не существует разрешимых обогащений теории дискретного линейного порядка без трансляционной теоремы, и что в каждом таком обогащении без трансляционной теоремы существует формула, способная выделить любое подмножество любого конечного множества. Это построение так же опровергает две более слабые гипотезы, утверждающие то же самое для расширений арифметики Пресбургера. Кроме того, далее мы строим теории, опровергающие одну из гипотез из работы Болдвина и Бенедикта.
18. С.М.Дудаков Псевдоконечная однородность, изолированность и сводимость // Матем. заметки, Т.81, вып. 4, 2004, С.515-527. doi: 10.1134/S0001434607030224
    Ранее установлено (Дудаков С.М., Тайцлин М.А.), что из сводимости некоторых моделей теории следует второе свойство псевдоконечной однородности для этой теории. Здесь мы доказываем обратное: из любого (первого или второго) свойства псевдоконечной однородности теории следует сводимость некоторых ее моделей, и, следовательно, второе свойство изолированности. Это доказывает также эквивалентность вторых свойств изолированности и псевдоконечной однородности, что контрастирует с тем, что первое свойство псевдоконечной однородности является более общим, чем первое свойство изолированности (Белеградек О.В., Столбоушин А.П., Тайцлин М.А.).
19. С.М.Дудаков Достаточные условия эффективной трансляции локально генерических запросов, // Фундаментальная и прикладная математика. 2009. Т. 15. № 5. С. 49-61.
    Данная работа является продолжением исследований по теории языков запросов первого порядка к базам данных. Ранее было установлено, что во многих разрешимых теориях имеет место трансляционная теорема: каждый локально генерический запрос эквивалентен некоторому ограниченному, но вопрос о возможности эффективного нахождения этого запроса почти не исследовался. Используя полученные автором ранее результаты, мы предлагаем метод эффективного нахождения этих запросов для широкого класса теорий, который включает арифметику Пресбургера и теорию действительных чисел.
20. С.М.Дудаков МОНАДИЧЕСКИЕ СОСТОЯНИЯ НАД УПОРЯДОЧЕННЫМ УНИВЕРСАЛЬНЫМ СЛУЧАЙНЫМ ГРАФОМ И КОНЕЧНЫЕ АВТОМАТЫ // Известия Российской академии наук. Серия математическая. 2011. Т. 75. № 5. С. 47-64. doi: 10.4213/im4077
    В работе продолжено изучение выразительной силы языка логики предикатов для конечных алгебраических систем, вложенных в бесконечные, которое было начато в работах М.А.Тайцлина, М.Бенедикта, Л.Либкина и др. Изучено, какие свойства конечной монадической системы можно выразить с помощью формул, если вложить такую систему в линейно упорядоченный произвольным образом случайный граф. В работе используется представление Бюхи для связи монадических состояний и формальных языков. Показано, что если ограничиться рассмотрением только инвариантных в линейно упорядоченных случайных графах формул, то такие формулы соответствуют конечным автоматам. Продемонстрировано, что $=$-инвариантные формулы, выражающие собственные свойства вложенных систем, способны выразить только булеву комбинацию свойств вида "мощность пересечения одноместных предикатов принадлежит одной из конечного числа фиксированных конечных или бесконечных арифметических прогрессий."
21. 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.
22. С.М.Дудаков О БЕЗОПАСНОСТИ РЕКУРСИВНЫХ ЗАПРОСОВ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2012. № 4 (27). С. 71-80.
    В работе исследуется вопрос об определенности рекурсивных запросов на универсуме. В качестве модели рекурсивного запроса применяется оператор инфляционной фиксированной точки IFP. Исследованы основные свойства IFP-оператора и показано, что модели счетно-категоричных теорий являются безопасными.
23. С.М.Дудаков О БЕЗОПАСНОСТИ IFP-ОПЕРАТОРОВ И РЕКУРСИВНЫХ ЗАПРОСОВ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2013. № 2 (29). С. 5-13.
    В работе продолжается исследование об определенности рекурсивных запросов на универсуме. Ранее нами показано, что модели счетно-категоричных теорий безопасны. В данной работе мы показываем, что счетная категоричность необходимым условием не является, и предлагаем необходимые и достаточные условия безопасности IFP-оператора.
24. С.М.Дудаков НЕРАЗРЕШИМОСТЬ ПРОБЛЕМЫ ОПРЕДЕЛЕННОСТИ БИНАРНЫХ IFP-ОПЕРАТОРОВ ДЛЯ ТЕОРИИ ОДНОГО СЛЕДОВАНИЯ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2014. № 4. С. 7-15.
    В работе продолжается исследование определенности оператора инфляционной фиксированной точки. Показано, что проблема определенности бинарного IFP-оператора для теории следования алгоритмически неразрешима.
25. С.М.Дудаков СИЛЬНАЯ МИНИМАЛЬНОСТЬ И IFP-БЕЗОПАСНОСТЬ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2015. № 3. С. 25-32.
    В работе продолжено исследование IFP-безопасности теорий. Доказано, что среди полных конечно аксиоматизируемых сильно минимальных теорий IFP-безопасных нет.
26. 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.
27. С.М.Дудаков О выразительной силе логики одноместного транзитивного замыкания для дискретного порядка // Вестник Тверского государственного университета. Серия: Прикладная математика. 2017. № 4. С. 25-33. doi: 10.26456/vtpmk186
    В работе показано, что в теории дискретного линейного порядка с одноместным оператором транзитивного замыкания с помощью формул длины n можно представить сложение, умножение и экспоненту для натуральных чисел вплоть до H2(n), где H2(n) - гиперэкспонента.
28. С.М.Дудаков О сложности разрешения теории следования с унарным оператором транзитивного замыкания // "Актуальные проблемы прикладной математики, информатики и механики" сборник трудов Международной научно-технической конференции. Воронежский государственный университет, 2017 Воронеж: "Научно-исследовательские публикации"; Общество с ограниченной ответственностью "Вэлборн", 2017. С.1503-1507.
    Доказано, что в теории следования с унарным оператором транзитивного замыкания для любого разрешающего алгоритма найдётся бесконечно много формул f, на которых он будет работать не менее H2(O(n)) шагов. Здесь n - длина формулы f, H2 - функция гиперэкспоненты по основанию 2.
29. С.М.Дудаков Использование итеративных операторов в классических логических теориях // "Алгебра и теория алгоритмов" Сборник материалов Всероссийской конференции, посвящённой 100-летию факультета математики и компьютерных наук Ивановского государственного университета. Иваново : Ивановский государственный университет, 2018. С.145-147
    Мы показываем связь конечности IFP-операторов с разрешимостью IFP-теории.
30. С.М.Дудаков 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.
31. С.М.Дудаков О безопасности одно и многоместных 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-операторов произвольной местности.
32. С.М.Дудаков О границах трансфинитного построения инфляционной неподвижной точки // Вестник Тверского государственного университета. Серия: Прикладная математика. 2018. № 3. С. 72-80. doi: 10.26456/vtpmk510
    В работе показано, что если универсум допускает существование оператора инфляционной неподвижной точки, который не вычисляется за конечное число шагов, то существуют операторы инфляционной неподвижной точки, требующие для своего трансфинитного построения произвольного числа шагов вплоть до ординала $\omega^\omega$ в любом универсуме. Для дискретного порядка продемонстрирована возможность построения за произвольное число шагов.
33. С.М.Дудаков 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.
34. 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.
35. С.М. Дудаков Об алгоритмических свойствах алгебры конечных подмножеств некоторых уноидов // Вестник Тверского государственного университета. Серия: Прикладная математика. 2019. № 4. С. 108-116. DOI: 10.26456/vtpmk550
    В работе показано, что если рассмотреть алгебру из некоторых уноидов в виде "кустов", соединённых в бесконечную линию, и построить алгебру её конечных подмножеств, то полученная система имеет теорию, допускающую эффективную элиминацию кванторов независимо от исходной. Таким образом, показано, что теория алгебры конечных подмножеств может быть существенно проще алгоритмически, чем теория исходной, а операция объединения для алгебр подмножеств является существенной для алгоритмических свойств.
36. С.М. Дудаков О неразрешимости алгебры односимвольных языков с операцией конкатенации // Материалы конференции "Алгебра и математическая логика: теория и приложения". Казань: Изд-во КФУ, 2019. С.101-103.
    Как известно, теория языка всех слов с операцией конкатенации неразрешима при наличии хотя бы двух символов (Гжегорчик, 2000). Для односимвольного алфавита соответствующая алгебра изоморфна аддитивному моноиду натуральных чисел, поэтому имеет разрешимую теорию. Возникает вопрос: что можно сказать о теории, в которой классические словарные операции, например, конкатенация, применяются не к отдельным словам, а к целым языкам. В качестве носителя в этом случае выступает какое-либо множество языков, обладающее необходимыми свойствами замкнутости. Одним из наиболее "естественных" является класс автоматных языков, который замкнут относительного очень многих действий (Хопкрофт, 2013). В работе (Дудаков, Карлов, 2019) показано, что если сигнатура включает в себя объединение, а также ещё хотя бы одну из операций: конкатенацию или итерацию, то теория множества автоматных языков будет неразрешимой даже для однобуквенного алфавита. Более того, продемонстрировано, что степень неразрешимости такой теории эквивалентна полной элементарной арифметике. Мы усиливаем этот результат, доказывая, что одной операции конкатенации языков достаточно, чтобы такая теория класса регулярных языков была алгоритмически эквивалентна полной элементарной арифметике.
37. С.М. Дудаков 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.
38. С.М. Дудаков 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.
39. 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.
40. С.М.Дудаков. Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков // Вестник Тверского государственного университета. Серия: Прикладная математика. 2020. № 4. С. 5-13. DOI: 10.26456/vtpmk601
    Мы рассматриваем алгебру всех конечных языков над многосимвольным алфавитом с операцией конкатенации. Ранее было показано, что если взять подобную алгебру, но состоящую из всех регулярных многосимвольных языков, то в ней можно интерпретировать алгебру регулярных односимвольных языков, откуда следует, что теория обеих этих алгебр эквивалентна элементарной арифметике. В настоящей работе мы доказываем аналогичный результат для алгебры конечных языков: в ней определима подалгебра односимвольных языков, а сама она имеет теорию алгоритмически эквивалентную элементарной арифметике.
41. С.М.Дудаков. Об алгоритмической неразрешимости теории конечных подмножеств некоторых моноидов // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов МеждуА43 народной научной конференции, Воронеж, 7–9 декабря 2020 г. – Воронеж : Издательство «Научно-исследовательские публикации», 2021. – С. 1602-1607. - ISBN 978-5-6045486-1-5
    Мы рассматриваем произвольные коммутативные моноиды с сокращением, содержащие элементы бесконечного порядка. На них мы обобщаем результат полученный нами ранее для циклического моноида: конечные подмножества в таких моноидах сами образуют моноид, в котором интерпретируется элементарная арифметика. Следовательно, теория конечных подмножеств таких моноидов неразрешима.
42. 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.
43. С.М.Дудаков. О теории моноида конечных подмножеств для одной абелевой группы кручения // Вестник Тверского государственного университета. Серия: Прикладная математика. 2021. № 2. С. 39-55. DOI: 10.26456/vtpmk615
    Ранее был доказан следующий результат: если абелева группа G не является группой кручения, то теория моноида ее конечных подмножеств позволяет интерпретировать элементарную арифметику. В настоящей работе мы приводим пример, который показывает, что аналогичный результат можно получить и, по крайней мере, для некоторых групп кручения.
44. 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.
45. С.М.Дудаков. О конечных фигурах в линейных пространствах над полями конечной характеристики // Актуальные проблемы прикладной математики, информатики и механики : Сборник трудов Международной научной конференции, Воронеж, 13–15 декабря 2021 года. – Воронеж: Общество с ограниченной ответственностью "Вэлборн", 2022. – С. 1564-1570. EDN: DOVLIJ
    В работе изучаются алгебры, которые построены из линейных пространств над полями конечной характеристики с помощью перехода к алгебре конечных подмножеств. Доказывается, что при одновременном использовании для фигур поэлементного сложения и теоретико-множественных действий появляется возможность интерпретации элементарной арифметики. Далее этот результат применяется для того, чтобы показать аналогичную возможность интерпретации арифметики при рассмотрении конечных подмножеств бесконечных абелевых групп конечной экспоненты.
46. С.М.Дудаков. О йонсоновских многообразиях и квазимногообразиях // Вестник ТвГУ. Серия: Прикладная математика. 2022. № 4. С. 5-10. DOI: 10.26456/vtpmk650
    В работах некоторых авторов было введено понятие йонсоновского многообразия и квазимногообразия и для таких классов алгебраических систем доказаны разного рода утверждения. Мы показываем, что на самом деле йонсоновские многообразия и квазимногообразия ограничиваются всего лишь классами множеств и либо пунктированных множеств в зависимости от сигнатуры. Таким образом, результаты, полученные в упомянутых выше работах другими исследователями, является тривиальными.
47. Н.В.Авхимович, С.М.Дудаков. Разрешимость теории конечных подмножеств безатомных булевых алгебр // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научной конференции, Воронеж, 12–14 декабря 2022 года / Воронежский государственный университет. – Воронеж: Научно-исследовательские публикации, 2023. – С. 1326-1331. EDN: kkychz
48. Н.В.Авхимович, С.М.Дудаков. Разрешимость теории конечных подмножеств безатомных булевых алгебр // Вестник Тверского государственного университета. Серия: Прикладная математика. – 2023. – № 1. – С. 24-35. DOI: 10.26456/vtpmk656
    В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория построенной таким образом новой системы сводится к теории безатомных булевых алгебр. Следовательно, так же как и теория исходной системы, теория новой системы оказывается разрешимой.
49. С.М.Дудаков. О моноиде с разрешимой теорией конечных подмножеств // Вестник Тверского государственного университета. Серия: Прикладная математика. – 2024. – № 2. – С. 27-38. DOI: 10.26456/vtpmk708
    В наших предыдущих работах мы продемонстрировали, что теория конечных подмножеств различных ассоциативных алгебр позволяет интерпретировать элементарную арифметику, в частности, она неразрешима. Например, это было показано для любых бесконечных абелевых групп. Возникает естественный вопрос: можно ли обобщить этот результат на более широкий класс алгебр, скажем, все коммутативные моноиды. В некоторых случаях нами ответ тоже получен ранее: для коммутативных моноидов с сокращением, имеющим элемент бесконечного порядка или произвольных абелевых групп. Сейчас же мы продемонстрируем, что не для всяких коммутативных моноидов это верно. Более того, мы дадим описание конструкции, которая позволяет строить такого рода системы из разного рода исходных алгебр. Вместе с тем, будут указаны и некоторые границы её применимости.
50. Н.В.Авхимович, С.М.Дудаков. Разрешимость теории конечных подмножеств атомных булевых алгебр // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научной конференции, Воронеж, 04–06 декабря 2023 года. – Воронеж: Общество с ограниченной ответственностью "Вэлборн", Издательство «Научно-исследовательские публикации», 2024. – С. 1355-1361. EDN: idpehk
    Мы рассматриваем алгебраические системы, где в качестве носителя берем конечные подмножества атомной булевой алгебры. Для полученной системы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество меньше другого в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория построенной таким образом новой системы может быть интерпретирована в теории исходной алгебры. Следовательно, как и теория исходной системы, теория новой системы оказывается разрешимой.
51. S.M.Dudakov. On undecidability degree of theory of figures in linear spaces // Mathematics and Theoretical Computer Science. – 2025. – Vol. 2, No. 4. – P. 51-65. – DOI: 10.26907/2949-3919.2024.4.51-65
    Мы изучаем аддитивную теорию произвольных фигур в линейных пространствах, т.е. теорию множеств точек/векторов, на которые естественным образом распространена операция сложения. Наш основной результат: если линейное пространство бесконечно, то аддитивная теория фигур в нем позволяет интерпретировать арифметику второго порядка и, следовательно, имеет не меньшую степень неразрешимости. Для счетно бесконечных пространств мы доказываем обратный результат: теория фигур в них может быть проинтерпретирована в арифметике второго порядка, следовательно, две такие теории алгоритмически эквивалентны. Для несчетных пространств последний вопрос остается открытым; мы показываем, что для пространств разных мощностей аддитивные теории фигур в них могут не быть элементарно эквивалентны.
52. С.М.Дудаков. Проблемы алгоритмической разрешимости и аксиоматизации алгебры конечных подмножеств для бинарных операций // Изв. РАН. Сер. матем. - 2025. - Т.89:2 . С. 3–24. DOI: 10.4213/im9579
    Рассматриваются алгебры конечных подмножеств, когда исходная алгебра является бесконечным группоидом. Доказывается, что для линейных пространств над полями конечной характеристики теория построенной алгебры алгоритмически эквивалентна элементарной арифметике. Далее этот результат обобщается на произвольные бесконечные абелевы группы. В качестве следствия получается, что общая теория классов всех алгебр конечных подмножеств имеет степень неразрешимости не меньшую, чем элементарная арифметика, для широкого круга исходных алгебр: абелевых групп, произвольных групп, моноидов, полугрупп, группоидов. Это также доказывает невозможность рекурсивной аксиоматизации теорий таких классов. Другим следствием является неразрешимость и невозможность рекурсивной аксиоматизации теории решётки подалгебр для абелевых групп конечной экспоненты, а также — теорий классов таких решёток для групп, моноидов и полугрупп.
53. С.М.Дудаков. О теориях алгебр подмножеств и решёток подпространств в конечных линейных пространствах // Вестник Тверского государственного университета. Серия: Прикладная математика. – 2025. – № 1. – С. 5-13. DOI: 10.26456/vtpmk728
    В наших предыдущих работах мы видели, что теории фигур и подпространств для бесконечных линейных пространств имеют высокую степень неразрешимости: они допускают интерпретацию элементарной арифметики, а в случае бесконечных фигур - даже арифметики второго порядка. В случае конечных линейных пространств эти утверждения конечно же неверны, так как мы можем построить алгоритм, перебирающий все конечные линейные пространства и выдающий все формулы, модель которых нашлась. Следовательно, для конечных линейных пространств теории фигур и подпространств принадлежат классу Π₁ - дополнений рекурсивно перечислимых множеств. В настоящей работе мы показываем, что эти теории являются полными задачами для класса Π₁, то есть по-прежнему неразрешимы и не рекурсивно аксиоматизируемы.
54. Complexity of Lambek Calculi with Modalities and of Total Derivability in Grammars / S. M. Dudakov, B. N. Karlov, S. L. Kuznetsov, E. M. Fofanova // Algebra and Logic. – 2021. – Vol. 60, No. 5. – P. 308-326. – DOI: 10.1007/s10469-021-09657-5
    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.
55. S.M.Dudakov. On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces // Lobachevskii Journal of Mathematics. – 2025. – Vol. 46, No. 12. – P. 6092-6102. – DOI: 10.1134/S1995080225613815
    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.
56. С.М.Дудаков. О задаче тотальной выводимости пустого слова в контекстно-свободной грамматике // Актуальные проблемы прикладной математики, информатики и механики : cборник трудов Международной научной конференции, Воронеж, 02–04 декабря 2024 года. – Воронеж: Научно-исследовательские публикации, 2025. – С. 1321-1324. – EDN: ZCSDZK
    Мы изучаем задачу тотальной выводимости пустого слова в контекстно-свободной грамматике. Б. Н. Карловым показано, что если тотальность задавать произвольным множеством правил, то такая задача будет NP-полной. Наш же результат показывает, что при классическом понимании тотального вывода, то есть применении всех правил грамматики, ответ может быть получен за полиномиальное время. Для этого мы предлагаем алгоритм, который по KC -грамматике строит мультиграф, затем - его конденсацию, а дальше проверяет некоторые свойства путей в этой конденсации, что можно сделать классическими алгоритмами за полиномиальное время.
57. С.М.Дудаков. О сложности проблемы тотальной выводимости в неукорачивающих и контекстно-свободных грамматиках / С. М. Дудаков, Б. Н. Карлов // Доклады Российской академии наук. Математика, информатика, процессы управления. – 2025. – Т. 524, № 1. – С. 11-18. – DOI: 10.7868/S3034504925040024
    В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.
58. S.M.Dudakov. On the Theory of Subalgebra Lattices for Arbitrary Groupoids // Mathematical Notes. – 2026. – Vol. 119, No. 1-2. – P. 236-245. – DOI: 10.1134/S0001434626600420
    The theory of subalgebra lattices for the class of arbitrary groupoids, that is, algebras with a binary operation, is investigated. It has earlier been proved that similar lattice theories for the classes of Abelian groups, of all groups, of monoids, and of semigroups admit an interpretation of elementary arithmetic. Thus, they are undecidable and have no recursive axiomatization. For the class of all groupoids, the question remained open, because the proof used the associativity of the binary operation. In the present paper, a new method which makes it possible to overcome this limitation is proposed; it applies to arbitrary groupoids. Thus, it is possible to interpret elementary arithmetic in the theory of subalgebra lattices for the class of all groupoids. Therefore, the theory of subalgebra lattices for the class of all groupoids is algorithmically undecidable and has no recursive axiomatization. Some results on the upper bound for the degree of undecidability of lattice theories for groupoids are also obtained.
59. С.М.Дудаков. О задаче 1-выводимости слов в контекстно-свободной грамматике // Актуальные проблемы прикладной математики, информатики и механики : сборник материалов Международной научной конференции «Актуальные проблемы прикладной математики, информатики и механики» (г. Воронеж, 1–3 декабря 2025 г.). — Воронеж : ООО «Издательство «Прометей»», 2026. — С. 1580-1583.
    Ранее нами рассматривалась задача тотальной выводимости в грамматиках разного вида, то есть когда в выводе требуется применить все правила хотя бы по одному разу. Эта задача первоначально возникла для аксиоматизации некоторых форм исчисления Ламбека, но она же может интерпретироваться и как, например, задача о поведении событийно-ориентированной системы. В настоящей работе мы рассматриваем противоположную ситуацию, когда есть верхние ограничения на количества применений правил. Наш основной результат: даже в простейшем случае, когда каждое правило можно применить не более чем единожды, а выводимое слово пусто, такая задача будет NP-полной, если не делать ограничений на количество нетерминалов в грамматике. Если последнее ограничение есть, то есть алгоритм, решающий задачу за полиномиальное время.

Научно-методические публикации:

1. С.М.Дудаков. Информатика. // Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК ТвГУ по основам фундаментальных и компьютерных знаний: Учебно-методический сборник. Тверь: ТвГУ. 2002. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
2. С.М.Дудаков. Математическое введение в информатику: Учебное пособие. Тверь: ТвГУ. 2003. - 240c. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
3. С.М.Дудаков. Информатика. // Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК ТвГУ по основам фундаментальных и компьютерных знаний: Учебно-методический сборник. Тверь: ТвГУ. 2007. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
4. С.М.Дудаков. Языки программирования и методы трансляции. // Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК ТвГУ по основам фундаментальных и компьютерных знаний: Учебно-методический сборник. Тверь: ТвГУ. 2007. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
5. С.М.Дудаков. Основы теории моделей: Учебник. Тверь: ТвГУ. 2013. - 480c.
6. Захарова И.В., Дудаков С.М., Язенин А.В., Солдатенко И.С. О методических аспектах разработки примерных образовательных программ высшего образования // Образовательные технологии и общество. 2015. Т. 18. № 3. С. 330-354.
7. Захарова И.В., Дудаков С.М., Язенин А.В. О разработке примерного учебного плана по УГСН «Компьютерные и информационные науки» в соответствии с профессиональными стандартами // Вестник Тверского государственного университета. Серия: Педагогика и психология. 2016. № 2. С. 84-100. 13
8. Захарова И.В., Дудаков С.М., Язенин А.В. О разработке магистерской программы по УГСН «Компьютерные и информационные науки» в соответствии с профессиональными стандартами // Вестник Тверского государственного университета. Серия: Педагогика и психология. 2016. № 3. С. 114-126.
9. Захарова И.В., Дудаков С.М., Солдатенко И.С. Проектирование образовательных программ в области икт с учётом профессиональных стандартов // Инженерное образование. 2017. № 21. С. 140-144.
10. Дудаков С.М., Захарова И.В. Мониторинг сформированности математических компетенций у студентов it-специальностей // Инженерное образование. 2017. № 21. С. 90-95.
11. Захарова И.В., Дудаков С.М. Сравнительный анализ образовательных стандартов ФГОС ВО 3+ и ФГОС ВО 3++ по направлению подготовки "Прикладная математика и информатика" // Образовательные технологии и общество, 2019, 22(4), с.96-105.
12. С.М.Дудаков, Б.Н.Карлов. Математическое введение в информатику : учебник по дисциплине «Теоретические основы информатики» 2-е издание, исправленное и дополненное. Тверь: ТвГУ. 2017. - 320c.
13. Дехтярь М.И. Лекции по дискретной математике [Электронный ресурс] : учебник / Дехтярь М.И., Дудаков С.М., Карлов Б.Н. - Изд. 2-е, перераб. и доп. - Тверь : Тверской государственный университет, 2019. - 512с.
14. С.М.Дудаков. Универсальная алгебра : учебное пособие. Тверь: ТвГУ. 2019. - 112c.
15. Дудаков С.М. Математическое введение в информатику : учебник по дисциплине "Теоретические основы информатики" / С. М. Дудаков, Б. Н. Карлов. - Изд. 3-е, испр. и доп. - Тверь : Тверской государственный университет, 2020. - 320с.
16. Дехтярь М.И. Сборник задач по множествам, булевым функциям и математической логике : учебное пособие / М. И. Дехтярь, С. М. Дудаков, Б. Н. Карлов. - Тверь : Тверской государственный университет, 2020. - 128с.
17. Дехтярь М. И. Лекции по дискретной математике : Учебник / М. И. Дехтярь, С. М. Дудаков, Б. Н. Карлов. – 3-е издание, исправленное и дополненное. – Тверь : Тверской государственный университет, 2021. – 528 с.
18. Дехтярь М. И. Задачник по дискретной математике : учебное пособие / М. И. Дехтярь, С. М. Дудаков, Б. Н. Карлов. – 2-е издание, переработанное и дополненное. – Тверь : Тверской государственный университет, 2021. – 368 с.

Читаемые курсы

• Дискретная математика
• Математическая логика и теория алгоритмов
• Общая алгебра
• Прикладная алгебра и теория чисел
• История и методология математики и информатики

Ученики, имеющие ученую степень

• Снятков Алексей Сергеевич, кандидат физико-математических наук, Ярославский государственный университет им.Демидова, 2012
• Золотов Александр Сергеевич, кандидат физико-математических наук, Приволжский (Казанский) федеральный университет, 2017
• Секорин Всеслав Станиславович, кандидат физико-математических наук, Приволжский (Казанский) федеральный университет, 2024