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)
2024
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
2023
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
2022
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
2021
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
2017
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
2015
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.
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
22.
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
23.
S. M. Dudakov, “Monadic structures over an ordered universal random graph and finite automata”, Izv. Math., 75:5 (2011), 915–932
24.
S. M. Dudakov, “Sufficient conditions for effective translation of locally generic queries”, J. Math. Sci., 172:5 (2011), 654–662
2009
25.
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
26.
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
27.
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
28.
S. M. Dudakov, “Pseudofinite Homogeneity, Isolation, and Reducibility”, Math. Notes, 81:4 (2007), 456–466
2006
29.
S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Russian Math. Surveys, 61:2 (2006), 195–253
30.
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.
S. M. Dudakov, “The collapse theorem for theories of $I$-reducible algebraic systems”, Izv. Math., 68:5 (2004), 911–933
32.
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
33.
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
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 (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
2024
Contact us: