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 decidability and axiomatizability of finite subset algebra for binary operations”, Izv. RAN. Ser. Mat. (to appear)
2.
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
3.
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
4.
S. M. Dudakov, “On Undecidability of Finite Subsets Theory for Torsion Abelian Groups”, Mathematics, 10:3 (2022), 533 , 14 pp.
5.
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
6.
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
8.
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
9.
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
11.
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
13.
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)
S. M. Dudakov, “On safety of unary and non-unary IFP-operators”, Model. Anal. Inform. Sist., 25:5 (2018), 525–533
17.
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
18.
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
19.
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
21.
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
22.
S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932
23.
S. M. Dudakov, “Sufficient conditions for effective translation of locally generic queries”, J. Math. Sci., 172:5 (2011), 654–662
24.
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
25.
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
26.
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
27.
S. M. Dudakov, “Pseudofinite Homogeneity, Isolation, and Reducibility”, Math. Notes, 81:4 (2007), 456–466
28.
S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Russian Math. Surveys, 61:2 (2006), 195–253
29.
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
30.
S. M. Dudakov, “The collapse theorem for theories of $I$-reducible algebraic systems”, Izv. Math., 68:5 (2004), 911–933
31.
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
32.
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
33.
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
39.
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
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
Contact us: