Теория сложности вычислений,
теория языков первого порядка,
теория баз данных
Научная биография:
Окончил Тверской госуниверситет в 1997 году. В 2000 году защитил кандидатскую диссертацию (мехмат МГУ), в 2004 году присвоено звание доцента. В 2007 защитил докторскую диссертацию (мехмат МГУ), в 2008 присуждена ученая степень доктора физико-математических наук.
Основные публикации:
S. M. Dudakov, B. N. Karlov, “On Decidability of Theories of Regular Languages”, Theory of Computing Systems, 65 (2021), 462–478
S. M. Dudakov, “On inflationary fix-point operators safety”, Lobachevskii Journal of Mathematics, 36:4 (2015), 328–331
С. М. Дудаков, “Монадические состояния над упорядоченным универсальным случайным графом и конечные автоматы”, Изв. РАН. Сер. матем., 75:5 (2011), 47–64; S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932
С. М. Дудаков, М. А. Тайцлин, “Трансляционные результаты для языков запросов в теории баз данных”, УМН, 61:2(368) (2006), 3–66; S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Russian Math. Surveys, 61:2 (2006), 195–253
M. Dekhtyar, A. Dikovsky, S. Dudakov, N. Spyratos, “Maximal state independent approximations to minimal real change”, AMAI, 33 (2001), 157–204
С. М. Дудаков, “Проблемы алгоритмической разрешимости и аксиоматизации алгебры конечных подмножеств для бинарных операций”, Изв. РАН. Сер. матем., 89:2 (2025) (в печати)
2024
2.
С. М. Дудаков, “О моноиде с разрешимой теорией конечных подмножеств”, Вестник ТвГУ. Серия: Прикладная математика, 2024, № 2, 27–38
2023
3.
Н. В. Авхимович, С. М. Дудаков, “Разрешимость теории конечных подмножеств безатомных булевых алгебр”, Вестник ТвГУ. Серия: Прикладная математика, 2023, № 1, 24–35
2022
4.
S. M. Dudakov, “On Undecidability of Finite Subsets Theory for Torsion Abelian Groups”, Mathematics, 10:3 (2022), 533 , 14 pp.
5.
С. М. Дудаков, “О йонсоновских многообразиях и квазимногообразиях”, Вестник ТвГУ. Серия: Прикладная математика, 2022, № 4, 5–10
2021
6.
S. M. Dudakov, B. N. Karlov, “On Decidability of Theories of Regular Languages”, Theory of Computing Systems, 65 (2021), 462–478
С. М. Дудаков, “О теории моноида конечных подмножеств для одной абелевой группы кручения”, Вестник ТвГУ. Серия: Прикладная математика, 2021, № 2, 39–55
С. М. Дудаков, Б. Н. Карлов, С. Л. Кузнецов, Е. М. Фофанова, “Сложность исчислений Ламбека с модальностями и тотальной выводимости в грамматиках”, Алгебра и логика, 60:5 (2021), 471–496; S. M. Dudakov, B. N. Karlov, S. L. Kuznetsov, E. M. Fofanova, “Complexity of Lambek calculi with modalities and of total derivability in grammars”, Algebra and Logic, 60:5 (2021), 308–326
S. M. Dudakov, “On undecidability of subset theory for some monoids”, International Conference “Applied Mathematics, Computational Science and Mechanics: Current Problems”, AMCSM 2020 (Voronezh, december, 07-09, 2020), Journal of Physics: Conference Series, 1902, 2021, 012060 , 12 pp.
С. М. Дудаков, “Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков”, Вестник ТвГУ. Серия: Прикладная математика, 2020, № 4, 5–13
С. М. Дудаков, “Об алгоритмических свойствах алгебры конечных подмножеств некоторых уноидов”, Вестник ТвГУ. Серия: Прикладная математика, 2019, № 4, 108–116
S. M. Dudakov, “On computational complexity of successor theory with unary transitive closure”, Journal of Physics: Conference Series, 1202 (2019), 012018 (to appear) , 6 pp.
14.
S. M. Dudakov, B. N. Karlov, “On Decidability of Regular Languages Theories”, 14th International Computer Science Symposium in Russia, CSR 2019 (Novosibirsk, Russia, July 1–5, 2019), LNCS, 11532, 2019, 119–130 (to appear)
Д. А. Архангельский, Б. С. Байжанов, О. В. Белеградек, В. Я. Беляев, Л. А. Бокуть, М. К. Валиев, С. К. Водопьянов, М. Гитик, Ю. Ш. Гуревич, Д. О. Дадеркин, А. М. Дехтярь, М. И. Дехтярь, А. Я. Диковский, С. М. Дудаков, Е. И. Зельманов, Б. И. Зильбер, С. Л. Крушкаль, С. С. Кутателадзе, Ю. В. Матиясевич, Г. Е. Минц, И. Х. Мусикаев, А. К. Ребров, Ю. Г. Решетняк, А. Л. Семенов, А. П. Столбоушкин, И. А. Тайманов, Б. А. Трахтенброт, “Михаил Абрамович Тайцлин (1936–2013)”, Сиб. электрон. матем. изв., 10 (2013), 54–65
2012
22.
С. М. Дудаков, “О безопасности рекурсивных запросов”, Вестник ТвГУ. Серия: Прикладная математика, 2012, № 4, 71–80
С. М. Дудаков, “Монадические состояния над упорядоченным универсальным случайным графом и конечные автоматы”, Изв. РАН. Сер. матем., 75:5 (2011), 47–64; S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932
С. М. Дудаков, “Достаточные условия эффективной трансляции локально генерических запросов”, Фундамент. и прикл. матем., 15:5 (2009), 49–61; S. M. Dudakov, “Sufficient conditions for effective translation of locally generic queries”, J. Math. Sci., 172:5 (2011), 654–662
25.
С. М. Дудаков, “Алгоритмическая сложность NP-трудных множеств”, Вестник ТвГУ. Серия: Прикладная математика, 2009, № 13, 97–101
2008
26.
С. М. Дудаков, “Эффективная трансляция расширенных $<$-инвариантных формул в $<$-ограниченные”, Вестник ТвГУ. Серия: Прикладная математика, 2008, № 10, 5–24
27.
С. М. Дудаков, “Эффективная трансляция расширенных $<$-инвариантных формул в $<$-ограниченные в арифметике Cеменова”, Вестник ТвГУ. Серия: Прикладная математика, 2008, № 8, 65–75
2007
28.
С. М. Дудаков, “Псевдоконечная однородность, изолированность и сводимость”, Матем. заметки, 81:4 (2007), 515–527; S. M. Dudakov, “Pseudofinite Homogeneity, Isolation, and Reducibility”, Math. Notes, 81:4 (2007), 456–466
С. М. Дудаков, М. А. Тайцлин, “Трансляционные результаты для языков запросов в теории баз данных”, УМН, 61:2(368) (2006), 3–66; S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Russian Math. Surveys, 61:2 (2006), 195–253
S. M. Dudakov, “Isolation and Reducibility Properties and the Collapse Result”, First International Computer Science Symposium in Russia, CSR 2006 (t. Petersburg, Russia, June 8–12. 2006), LNCS, 3967, 2006, 171–177
2004
31.
С. М. Дудаков, “Трансляционная теорема для теорий $I$-сводимых алгебраических систем”, Изв. РАН. Сер. матем., 68:5 (2004), 67–90; S. M. Dudakov, “The collapse theorem for theories of $I$-reducible algebraic systems”, Izv. Math., 68:5 (2004), 911–933
С. М. Дудаков, “Трансляционный результат для расширений арифметики Пресбургера одноместной функцией, согласованной со сложением”, Матем. заметки, 76:3 (2004), 362–371; S. M. Dudakov, “Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition”, Math. Notes, 76:3 (2004), 339–347
С. М. Дудаков, “Сложность обновлений дедуктивных баз данных с фиксированным ограничением целостности”, Вестник ТвГУ. Серия: Прикладная математика, 2003, № 1, 16–27
2001
34.
M. Dekhtyar, A. Dikovsky, S. Dudakov, N. Spyratos, “Maximal Expansions of Database Updates”, Foundations of Information and Knowledge Systems (Burg, Germany, February 14–17, 2000), LNCS, 1762, 2001, 72–87
M. Dekhtyar, A. Dikovsky, S. Dudakov, “On Complexity of Updates through Integrity Constraints”, Computational Logic — CL 2000 (London, UK, July 24–28, 2000), LNCS, 1861, 2000, 867–881
M. Dekhtyar, A. Dikovsky, S. Dudakov, N. Spyratos, “Monotone expansion of updates in logical databases”, Logic Programming and Nonmonotonic Reasoning (El Paso, Texas, USA, December 2–4, 1999), LNCS, 1730, 1999, 132–147
S. M. Dudakov, “The Concurrency Complexity for the Horn Fragment of Linear Logic”, LFCS97 (Ярославль, 1997), LNCS, 1234, 1997, 78–87
Доклады и лекции в базе данных Math-Net.Ru
1.
On properties of subset algebras С. М. Дудаков Вторая конференция Математических центров России. Секция «Математическая логика и теоретическая информатика» 7 ноября 2022 г. 17:30
2025
Обратная связь: