Computational complexity, first order logic, database theory
Main publications:
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
S. M. Dudakov, “On Subalgebra Lattice Theory for Arbitrary Groupoids”, Mat. Zametki, 119:2 (2026) (to appear)
2025
2.
S. M. Dudakov, “Problems of algorithmic decidability and axiomatizability of finite subset algebra for binary operations”, Izv. Math., 89:2 (2025), 221–241
3.
S. M. Dudakov, “O stepeni nerazreshimosti teorii figur v lineinykh prostranstvakh”, Matematika i teoreticheskie kompyuternye nauki, 2:4 (2025), 51–65
S. M. Dudakov, “On theories of the subsets algebra and the subspaces lattice for finite linear spaces”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2025, no. 1, 5–13
5.
S. M. Dudakov, B. N. Karlov, “On complexity of total derivability problem in noncontracting and context-free grammars”, Dokl. RAN. Math. Inf. Proc. Upr., 524 (2025), 11–18
2024
6.
S. M. Dudakov, “On Finite Subsets Monoid with Decidable Theory”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2024, no. 2, 27–38
2023
7.
N. V. Avkhimovich, S. M. Dudakov, “On decidability of finite subsets’ theory for dense linear order”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2023, no. 1, 24–35
2022
8.
S. M. Dudakov, “On Undecidability of Finite Subsets Theory for Torsion Abelian Groups”, Mathematics, 10:3 (2022), 533 , 14 pp.
S. M. Dudakov, “On Jonsson varieties and quasivarieties”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2022, no. 4, 5–10
2021
10.
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 theory of finite subsets monoid for one torsion abelian group”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2021, no. 2, 39–55
12.
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
13.
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.
S. M. Dudakov, “On definability of one-symbol languages in the monoid of finite languages with concatenation”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2020, no. 4, 5–13
15.
S. M. Dudakov, “On Undecidability of Concatenation Theory for One-Symbol Languages”, Lobachevskii Journal of Mathematics, 41:2 (2020), 168–175
S. M. Dudakov, “On algorithmic properties of finite subset algebra for some unoids”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2019, no. 4, 108–116
17.
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.
18.
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)
S. M. Dudakov, “On safety of unary and non-unary IFP-operators”, Model. Anal. Inform. Sist., 25:5 (2018), 525–533
21.
S. M. Dudakov, “On bound of transfinite construction of inflationary fixed point”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2018, no. 3, 72–80
2017
22.
S. M. Dudakov, “On expressive power of monadic transitive close logic over discrete order”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2017, no. 4, 25–33
2015
23.
S. M. Dudakov, “On inflationary fix-point operators safety”, Lobachevskii Journal of Mathematics, 36:4 (2015), 328–331
S. M. Dudakov, “On Safety Of IFP-Operators And Recursive Queries”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2013, no. 2, 5–13
25.
D. A. Archangelsky, B. S. Baizhanov, O. V. Belegradek, V. Ya. Belyaev, L. A. Bokut, M. K. Valiev, S. K. Vodopyanov, M. Gitik, Yu. S. Gurevich, D. O. Daderkin, A. M. Dekhtyar, M. I. Dekhtyar, A. Ya. Dikovsky, S. M. Dudakov, E. I. Zelmanov, B. I. Zilber, S. L. Krushkal, S. S. Kutateladze, Yu. V. Matiyasevich, G. E. Mints, I. Kh. Musikaev, A. K. Rebrov, Yu. G. Reshetnyak, A. L. Semenov, A. P. Stolboushkin, I. A. Taimanov, B. A. Trakhtenbrot, “Mikhail Abramovich Taitslin (1936–2013)”, Sib. Èlektron. Mat. Izv., 10 (2013), 54–65
2012
26.
S. M. Dudakov, “On safety of recursive queries”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2012, no. 4, 71–80
2011
27.
S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932
28.
S. M. Dudakov, “Sufficient conditions for effective translation of locally generic queries”, J. Math. Sci., 172:5 (2011), 654–662
2009
29.
S. M. Dudakov, “Algorithmic complexity of NP-hard sets”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2009, no. 13, 97–101
2008
30.
S. M. Dudakov, “Effective translation of extended $ <$ - invariant formulas in $ <$- bounded”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2008, no. 10, 5–24
31.
S. M. Dudakov, “Effective translation of extended $ <$ - invariant formulas in $ <$ -bounded in Semenov arithmetic”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2008, no. 8, 65–75
2007
32.
S. M. Dudakov, “Pseudofinite Homogeneity, Isolation, and Reducibility”, Math. Notes, 81:4 (2007), 456–466
2006
33.
S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Russian Math. Surveys, 61:2 (2006), 195–253
34.
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
35.
S. M. Dudakov, “The collapse theorem for theories of $I$-reducible algebraic systems”, Izv. Math., 68:5 (2004), 911–933
36.
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
37.
S. M. Dudakov, “The complexity of deductive database updates with a fixed restriction on data integrity”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2003, no. 1, 16–27
2001
38.
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 (Yaroslavl, 1997), LNCS, 1234, 1997, 78–87
Presentations in Math-Net.Ru
1.
On properties of subset algebras S. M. Dudakov Second Conference of Russian Mathematical Centers. Section «Mathematical Logic and Theoretical Computer Science» November 7, 2022 17:30
2026