Home page
Font:
A A A
Color:
A A A
Images:
Special mode Special mode Special mode

Clear mode

  Home page
Home page
Russian page
English page
Math-Net.Ru | Web of Science | Scopus | MathSciNet | zbMATH | Web-mail 

   
 About the Institute
 Staff publications
 Administration
 Academic Council
 Dissertation Councils
 Departments
Staff 
 Chair at MIPT
 Seminars
 Conferences
 Events
 Journals and Books
 In memoriam
 Photogallery
 Charter

    Address
8 Gubkina Str. Moscow,
119333, Russia
Tel.: +7(495) 984 81 41
Web site: www.mi-ras.ru
E-mail: steklov@mi-ras.ru

View Map
Directions

   

Department of Mathematical Logic. List of publications

Steklov Mathematical Institute staff Steklov Mathematical Institute staff and out-of-staff employees
| by years | scientific publications | by types |



   2027
1. D. S. Shamkanov, “(Non-)well-founded derivations in the provability logic GLP”, The Legacy of A.V. Kuznetsov in Logic, Algebra and the Foundations of Mathematics, Trends in Logic, 71, eds. Alex Citkin, Alexei Muravitsky, Springer Cham, 2027, 1–32 (to appear) https://link.springer.com/book/9783032194596

   2026
2. D. Ingram, A. Razborov, “On the Range of the Permanent of (\pm 1)-Matrices”, Linear Algebra and its Applications, 743 (2026), 271-285  crossref
3. Karim F. Shamazov, Alexey L. Talambutsa, “On orbit sets generated by semigroups of one-dimensional affine functions”, Expo. Math., 44:3 (2026), 125765, 11 pp., arXiv: 2507.06875  mathnet  crossref
4. P.Kiyashko, A.Talambutsa, “A simple algorithm for checking equivalence of counting functions on free monoids”, International Journal of Algebra and Computation, 2026, 1–22 (to appear), arXiv: 2407.10569  crossref
5. J. P. Aguilera, F. Pakhomov, “The logic of correct models”, Journal of Mathematical Logic, 26:2 (2026), 2550004, 20 pp. https://www.worldscientific.com/doi/abs/10.1142/S0219061325500047?casa_token=X9neTYK_oKsAAAAA:KRrf4ABca80xPxYhQJUTS7604-PZZORRJqYxkHjx-UcoWbiw_3MXroi79Uomn-XG3NXCXnaoCxkb, arXiv: 2402.15382  crossref
6. Daniyar Shamkanov, Cyclic proofs in the equational version of Primitive recursive arithmetic, 2026 (Published online), 10 pp., arXiv: https://arxiv.org/abs/2606.07166  crossref
7. S. O. Speranski, A. V. Grefenshtein, “On the complexity of first-order logics of probability”, Izv. Math., 90:4 (2026), 754–775  mathnet  crossref  crossref  mathscinet  adsnasa  isi  scopus
8. S. O. Speranski, “On the closure ordinals of infinitary probabilistic calculi”, Math. Notes, 120:3 (2026), 538–548  mathnet  crossref  crossref
9. V. E. Karpov, S. O. Speranskii, “O teorii naturalnykh chisel so standartnym poryadkom i svobodnoi ekvivalentnostyu”, Sibirskii matematicheskii zhurnal, 2026, 1–15 (to appear)
10. S. L. Kuznetsov, “Algorithmic complexity of theories with Kleene iteration”, Russian Math. Surveys, 81:1 (2026), 125–188  mathnet  crossref  crossref  mathscinet  adsnasa  isi  scopus
11. Stepan L. Kuznetsov, “On Lambek grammars with Kleene star”, Distributed Computing and Artificial Intelligence, Special Sessions I, 22nd International Conference (Lille, France, June 25–27, 2025), Lecture Notes in Networks and Systems, 1631, Springer, Cham, 2026, 85–95  crossref  isi  scopus
12. Max Kanovich, Stepan L. Kuznetsov, Andre Scedrov, “Complexity of equational theories for relational and language action lattices”, Relational and Algebraic Methods in Computer Science, 22nd International Conference, RAMiCS 2026 (Będlewo, Poland, April 7–10, 2026), Lecture Notes in Comput. Sci., 16526, eds. U. Fahrenberg, W. Fussner, L. Santocanale, Springer, 2026, 208–228  crossref  scopus 1
13. Stepan L. Kuznetsov, “On syntactic concept lattice models for the Lambek calculus and infinitary action logic”, J. Logic Comput., 36:1 (2026), exaf078, 23 pp., arXiv: 2510.24853  mathnet  crossref  zmath  isi  scopus
14. Stepan L. Kuznetsov, “A survey on language completeness of the Lambek calculus and its extensions”, Computational Linguistics, Information, Reasoning, and AI 2024, Stud. Comput. Intell., 1280, eds. R. Loukanova, Springer, 2026, 25–45  crossref
15. Anupam Das, Abhishek De, Stepan L. Kuznetsov, “Undecidability for semirings with fixed points”, 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026) (Lisbon, July 20–23, 2026), Leibniz Internat. Proc. in Inform., 378, eds. F. Pfenning, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2026, 15:1–15:18  crossref
16. Stepan L. Kuznetsov, “Complexity of reasoning in Kleene algebra with sum-of-letters hypotheses”, Automated Reasoning, 13th International Conference, IJCAR 2026 (Lisbon, July 26–29, 2026), Part II, Lecture Notes in Artif. Intell., 16689, eds. A. Biere et al., Springer, 2026, 161–177  crossref

   2025
17. G. Blekherman, A. Raymond, A. Razborov, F. Wei, On Domination Exponents for Pairs of Graphs, 2025, 20 pp., arXiv: 2506.12151
18. Izv. Math., 89:4 (2025), 758–861  mathnet  crossref  crossref  mathscinet  adsnasa  isi  scopus
19. S. V. Konyagin, V. Yu. Protasov, A. L. Talambutsa, “Unique expansions in number systems via refinement equations”, Sb. Math., 216:11 (2025), 1614–1627  mathnet  crossref  crossref  mathscinet  mathscinet  adsnasa  isi  scopus
20. A.Talambutsa, On the word problem for just infinite groups, 2025, 11 pp., arXiv: 2512.24266
21. Lev D. Beklemishev, Fedor N. Pakhomov, “Automatic structures and the problem of natural well-orderings”, Model Theory, Computer Science, and Graph Polynomials: Festschrift in honor of Johann A. Makowsky, Trends in Mathematics, eds. K. Meyer, A. Rabinovich, E. Ravve, A. Villaveces, Birkhäuser, 2025, 91–109, arXiv: 2407.10198  crossref 1
22. F. Pakhomov, G. Solda, “On Nash-Williams' Theorem regarding sequences with finite range”, Transactions of the AMS, 2025, 30 (to appear), arXiv: 2405.13842
23. Hanul Jeon, Patrick Lutz, Fedor Pakhomov, James Walsh, Ranking theories via encoded β-models, 2025, 21 pp., arXiv: 2503.20470
24. Fedor Pakhomov, Giovanni Soldà, Generalized Higman's Theorem and iterated ideals, 2025, 22 pp., arXiv: 2512.07685
25. Izv. Math., 89:2 (2025), 399–421  mathnet  crossref  crossref  mathscinet  adsnasa  isi  scopus
26. L. D. Beklemishev, D. S. Shamkanov, I. N. Smirnov, “Fragments of arithmetic and cyclic proofs”, Sb. Math., 216:10 (2025), 1339–1362  mathnet  crossref  crossref  mathscinet  adsnasa  isi  scopus
27. D. Shamkanov, (Non-)well-founded derivations in the provability logic GLP, 2025, 37 pp., arXiv: 2504.01388
28. Stanislav O. Speranski, “Sharpening complexity results in quantified probability logic”, Log. J. IGPL, 33:3 (2025), jzae114, 21 pp.  mathnet  crossref  mathscinet  isi 7
29. Stanislav O. Speranski, “An ‘elementary’ perspective on reasoning about probability spaces”, Log. J. IGPL, 33:2 (2025), jzae042, 23 pp.  mathnet  crossref  isi 5
30. S. O. Speranski, “On the decision problem for quantified probability logics”, Izv. Math., 89:3 (2025), 609–627  mathnet  crossref  crossref  mathscinet  adsnasa  isi  scopus
31. V. E. Karpov, S. O. Speranski, “On hereditarily undecidable fragments of basic elementary theories”, Math. Notes, 118:1 (2025), 95–107  mathnet  crossref  crossref  mathscinet  isi  scopus
32. Stepan L. Kuznetsov, Tikhon Pshenitsyn, Stanislav O. Speranski, “Reasoning from hypotheses in *-continuous action lattices”, J. Symb. Log., 2025, 1–39 (Published online), arXiv: 2408.02118  mathnet  crossref  isi 1
33. S. O. Speranski, “On Fitting’s modification of Kripke’s theory of truth”, Doklady Mathematics, 2025 (to appear)  mathnet  crossref  elib
34. S. N. Artemov, L. D. Beklemishev, S. S. Goncharov, Yu. L. Ershov, S. P. Odintsov, V. V. Rybakov, S. O. Speranski, V. B. Shehtman, V. F. Yun, “Larisa L'vovna Maksimova (obituary)”, Russian Math. Surveys, 80:3 (2025), 533–536  mathnet  crossref  crossref  mathscinet  adsnasa  isi
35. A. L. Semenov, M. A. Babenko, A. Ya. Belov, N. K. Vereshchagin, M. E. Vishnikin, E. E. Zolin, V. N. Krupski, S. L. Kuznetsov, V. A. Lyubetskii, A. A. Onoprienko, M. R. Pentus, S. F. Soprunov, A. A. Sorokin, V. B. Shehtman, T. L. Yavorskaya, “Chair of Mathematical Logic and Theory of Algorithms”, Moscow University Mathematics Bulletin, 80:1 (2025), 23–33  mathnet  crossref  crossref  elib
36. Mikhail Valinkin, Stepan L. Kuznetsov, “Relational models for the Lambek calculus with local contraction subexponentials”, J. Logic Comput., 35:4 (2025), exaf030, 21 pp.  mathnet  crossref  mathscinet  zmath  isi  scopus

   2024
37. A. A. Razborov, Mat. Pros., 33, MCCME, Moscow, 2024, 151–153  mathnet
38. Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii, “Logical Languages Accepted by Transformer Encoders with Hard Attention”, The Twelfth International Conference on Learning Representations, {ICLR} 2024, Vienna, Austria, May 7-11, 2024, OpenReview.net, 2024, 1-11 https://openreview.net/forum?id=gbrHZq07mq
39. Vladimir V. Podolskii and Dmitrii Sluch, “One-Way Communication Complexity of Partial XOR Functions”, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, LIPIcs, 2024, 116, 16 pp.  crossref
40. Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii, “Towards Simpler Sorting Networks and Monotone Circuits for Majority”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK, LIPIcs, 2024, 50, 18 pp.  crossref
41. Vladimir Podolskii, Victor Selivanov, “Complexity Aspects of the Extension of Wagner's Hierarchy to k-Partitions”, Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications, Electronic Proceedings in Theoretical Computer Science, 407, Open Publishing Association, 2024, 186–197  crossref
42. Alexander I. Bufetov, Gabriel Nivasch, Fedor Pakhomov, “Generalized fusible numbers and their ordinals”, Ann. Pure Appl. Logic, 175 (2024), 103355, 25 pp.  mathnet  crossref  mathscinet 1
43. Juvenal Murwanashyaka, Fedor Pakhomov, Albert Visser, “There are no minimal essentially undecidable theories”, J. Logic Comput., 34:6 (2024), 1159–1171  mathnet  crossref  mathscinet 5
44. J. P. Aguilera, F. Pakhomov, A. Weiermann, “Functorial fast-growing hierarchies”, Forum Math. Sigma, 12 (2024), 15, 16 pp.  mathnet  crossref  mathscinet 2
45. Anton Freund, Fedor Pakhomov, Giovanni Soldà, “The logical strength of minimal bad arrays”, Proc. Amer. Math. Soc., 152 (2024), 4993–5005, arXiv: 2304.00278  mathnet  crossref 2
46. Daniyar Shamkanov, “On algebraic and topological semantics of the modal logic of common knowledge $S4^C_I$”, Log. J. IGPL, 32:1 (2024), 164–179, arXiv: 2111.05676  mathnet  crossref  mathscinet 1
47. Daniyar Shamkanov, “On structural proof theory of the modal logic $K^+$ extended with infinitary derivations”, Log. J. IGPL, 2024, jzae121, 46 pp., arXiv: 2310.10309  mathnet  crossref  mathscinet  isi 3
48. A. V. Grefenshtein, S. O. Speranski, “On the quantified version of the Belnap–Dunn modal logic”, Sb. Math., 215:3 (2024), 323–354  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  scopus
49. S. O. Speranskii, Teoriya vnutrennikh mnozhestv: Aksiomaticheskii podkhod k nestandartnomu analizu, Lektsii letnei shkoly «Sovremennaya matematika», Izdatelstvo MTsNMO, Moskva, 2024, 32 pp. preprint  mathnet
50. S. L. Kuznetsov, “Algorithmic complexity for theories of commutative Kleene algebras”, Izv. Math., 88:2 (2024), 236–269  mathnet  crossref  crossref  mathscinet  zmath  zmath  adsnasa  isi  scopus
51. Stepan L. Kuznetsov, “Syntactic concept lattice models for infinitary action logic”, Logic, Language, Information, and Computation, 30th International Workshop, WoLLIC 2024 (Bern, Switzerland, June 10–13, 2024), Lecture Notes in Comput. Sci., 14672, Springer, Cham, 2024, 93–107  mathnet  crossref  mathscinet  zmath  isi  scopus 1
52. S. L. Kuznetsov, Algoritmicheskie voprosy dlya substrukturnykh logik s iteratsiei Klini, Diss. … dokt. fiz.-matem. nauk, Matematicheskii institut im. V. A. Steklova RAN, Moskva, 2024, 266 pp. (.pdf)
53. S. L. Kuznetsov, “Strong conservativity and completeness for fragments of infinitary action logic”, Sib. elektron. matem. izv., 21:2 (2024), 789–809  mathnet  crossref  mathscinet  scopus 2

   2023
54. Theodoros Papamakarios, Alexander Razborov, “Space characterizations of complexity measures and size-space trade-offs in propositional proof systems”, J. Comput. Syst. Sci., 137 (2023), 20–36  mathnet  crossref  mathscinet  isi 1
55. Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688  mathnet  crossref  mathscinet 4
56. Alexander Razborov, “Propositional Proof Complexity”, Proceedings of the 8th European Congress of Mathematics (Portoroz, 20–26 June 2021), EMS Press, 2023, 439-464 https://ems.press/content/book-files/28311
57. A. L. Talambutsa, T. Hartnick, “Efficient computations with counting functions on free groups and free monoids”, Sb. Math., 214:10 (2023), 1458–1499  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  scopus
58. Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii, “Constant-Depth Sorting Networks”, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz Internat. Proc. in Inform., 251, 2023, 43, 19 pp.  mathnet  crossref  mathscinet
59. J. P. Aguilera, F. Pakhomov, “The $\Pi^1_2$ consequences of a theory”, J. London Math. Soc., 107:3 (2023), 1045–1073, arXiv: 2109.11652  mathnet  crossref  mathscinet 2
60. Fedor Pakhomov, James Walsh, “Reducing $\omega$-model reflection to iterated syntactic reflection”, J. Math. Log., 23:2 (2023), 2250001, 38 pp.  mathnet  crossref  mathscinet  scopus 2
61. Anton Freund, Alberto Marcone, Fedor Pakhomov, Giovanni Soldà, Provable better quasi orders, 2023, 3 pp., arXiv: 2305.01066
62. J. P. Aguilera, F. Pakhomov, A. Weiermann, “Modern perspectives in Proof Theory”, Philos. Trans. R. Soc. A, 381 (2023), 20220020, 11 pp.  mathnet  crossref  mathscinet
63. J. P. Aguilera, F. Pakhomov, “The spectrum of $\Pi^1_3$-soundness”, Philos. Trans. R. Soc. A, 381 (2023), 20220013, 18 pp.  mathnet  crossref  mathscinet 1
64. Stepan L. Kuznetsov, Stanislav O. Speranski, “Infinitary action logic with multiplexing”, Studia Logica, 111:2 (2023), 251–280  mathnet  crossref  mathscinet  zmath  isi  scopus 7
65. S. O. Speranski, “Elementary invariants for quantified probability logic”, Doklady Mathematics, 107 (2023), 93–96  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  scopus
66. Stepan L. Kuznetsov, “Commutative action logic”, J. Logic Comput., 33:6 (2023), 1427–1462, arXiv: 2102.11639  mathnet  crossref  mathscinet  zmath  isi  scopus 4
67. Stepan L. Kuznetsov, “Complexity of the Lambek calculus and its extensions”, Logic and Algorithms in Computational Linguistics 2021, LACompLing2021, Stud. Comput. Intell., 1081, Springer, Cham, 2023, 1–29  mathnet  crossref  scopus
68. Stepan L. Kuznetsov, “Proof disbalancing for proving complexity results: towards infinitary focusing”, The Proof Society Summer School and Workshop 2023. Booklet of Abstracts (Barcelona, July 10–14, 2023), University of Barcelona, 2023, 69–72 (pdf)
69. Eben Blaisdell, Max Kanovich, Stepan L. Kuznetsov, Elaine Pimentel, Andre Scedrov, “Explorations in subexponential non-associative non-commutative linear logic”, Proceedings Modalities in substructural logics: Applications at the interfaces of logic, language and computation (AMSLO 2023), Ljubljana, Slovenia, August 7-8, 2023, Electron. Proc. Theor. Comput. Sci., 381, Open Publishing Association, 2023, 4–19, arXiv: 2308.05537v1  mathnet  crossref  mathscinet  zmath  isi  scopus
70. Stepan L. Kuznetsov, “On the complexity of reasoning in Kleene algebra with commutativity conditions”, Theoretical Aspects of Computing – ICTAC 2023, Lima, Peru, December 4–8, 2023, Lecture Notes in Comput. Sci., 14446, Springer, Cham, 2023, 83–99  mathnet  crossref  mathscinet  zmath  isi  scopus 8
71. Stepan L. Kuznetsov, “Relational models for the Lambek calculus with intersection and constants”, Log. Methods Comput. Sci., 19:4 (2023), 32, 27 pp., arXiv: 2210.00654  mathnet  crossref  mathscinet  zmath  isi  scopus 3

   2022
72. A. A. Razborov, “More about sparse halves in triangle-free graphs”, Sb. Math., 213:1 (2022), 109–128  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  scopus
73. Alexander Razborov, “An extremal problem motivated by triangle-free strongly regular graphs”, J. Comb. Theory, Ser. B, 155 (2022), 52–82  mathnet  crossref  mathscinet  scopus 1
74. Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-based proof systems with the ordered decision strategy”, SIAM J. Comput., 51:4 (2022), 1368–1399  mathnet  crossref  mathscinet 1
75. A. A. Razborov, Improved Convergence Guarantees for Shallow Neural Networks, 2022, arXiv: 2212.02323
76. Theodoros Papamakarios, Alexander Razborov, “Space characterizations of complexity measures and size-space trade-offs in propositional proof systems”, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), July 4–8, 2022, Paris, France, Leibniz Internat. Proc. in Inform., 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022, 100–20  mathnet  crossref  mathscinet;
77. Laurent Bartholdi, Thorsten Groth, Igor Lysenok, “Commutator width in the first Grigorchuk group”, Groups Geom. Dyn., 16:2 (2022), 493–522  mathnet  crossref  mathscinet  isi 4
78. Alexander Kolpakov, Alexey Talambutsa, “On free semigroups of affine maps on the real line”, Proc. Amer. Math. Soc., 150:6 (2022), 2301–2307, arXiv: 2105.09387  mathnet  crossref  mathscinet  scopus 3
79. Jean-Camille Birget, Alexey L. Talambutsa, “The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups”, Int. J. Algebra Comput., 32:6 (2022), 1261–1274, arXiv: 2112.02408  mathnet  crossref  mathscinet
80. Alexander Kolpakov, Alexey Talambutsa, “Growth rates of Coxeter groups and Perron numbers”, Int. Math. Res. Not. IMRN, 2022:19 (2022), 14675–14696, arXiv: 1912.05608  mathnet  crossref  mathscinet  isi
81. Anastasiya Chistopolskaya, Vladimir V. Podolskii, “On the Decision Tree Complexity of Threshold Functions”, Theory Comput. Syst., 66 (2022), 1074–1098  mathnet  crossref  mathscinet 2
82. Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii, Michael Zakharyaschev, “A tetrachotomy of ontology-mediated queries with a covering axiom”, Artif. Intell., 309 (2022), 103738, 46 pp.  mathnet  crossref  mathscinet 1
83. Vladimir Podolskii, Nikolay V. Proskurin, “Polynomial threshold functions for decision lists”, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz Internat. Proc. in Inform., 248, 2022, 52:1–52:12  mathnet  crossref  mathscinet
84. Alexander Kozachinskiy, Vladimir Podolskii, “Multiparty Karchmer–Wigderson games and threshold circuits”, Theory Comput., 18 (2022), 15, 33 pp.  mathnet  crossref  mathscinet  isi
85. S. O. Speranski, F. N. Pakhomov, “On the coprimeness relation from the viewpoint of monadic second-order logic”, Izv. Math., 86:6 (2022), 1225–1239  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  scopus
86. Lev D. Beklemishev, Fedor N. Pakhomov, “Reflection algebras and conservation results for theories of iterated truth”, Ann. Pure Appl. Logic, 173:5 (2022), 103093, 41 pp.  mathnet  crossref  mathscinet 11
87. Fedor Pakhomov, Albert Visser, “Finitely axiomatized theories lack self-comprehension”, Bull. Lond. Math. Soc., 54:6 (2022), 2513–2531, arXiv: 2109.02548  mathnet  crossref  mathscinet 4
88. Stepan L. Kuznetsov, Stanislav O. Speranski, “Infinitary action logic with exponentiation”, Annals of Pure and Applied Logic, 173:2 (2022), 103057, 29 pp., arXiv: 2001.06863  mathnet  crossref  mathscinet  zmath  isi  elib  scopus 15
89. S. O. Speranski, “Some remarks on Došen's logic N and its extensions”, Sib. elektron. matem. izv., 19:2 (2022), 562–577  mathnet  crossref  mathscinet  isi  elib  scopus
90. Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Language models for some extensions of the Lambek calculus”, Inform. and Comput., 287 (2022), 104760, 16 pp., arXiv: 2008.00070  mathnet  crossref  mathscinet  zmath  isi  scopus 8
91. Max I. Kanovich, Stepan G. Kuznetsov, Stepan L. Kuznetsov, Andre Scedrov, “Decidable fragments of calculi used in CatLog”, Natural Language Processing in Artificial Intelligence — NLPinAI 2021, Stud. Comput. Intell., 999, Springer, Cham, 2022, 1–24  mathnet  crossref  scopus 1
92. Stepan L. Kuznetsov, “Reasoning in commutative Kleene algebras from *-free hypotheses”, Logica Yearbook 2021, College Publications, London, 2022, 99–113  mathscinet  isi
93. Eben Blaisdell, Max Kanovich, Stepan L. Kuznetsov, Elaine Pimentel, Andre Scedrov, “Non-associative, non-commutative multi-modal linear logic”, Automated Reasoning, 11th International Conference, IJCAR 2022 (Haifa, Israel, August 8–10, 2022), Lecture Notes in Comput. Sci., 13385, Springer, Cham, 2022, 449–467  mathnet  crossref  mathscinet  zmath  isi  scopus 4

   2021
94. Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2021), 69-92  mathnet  crossref  mathscinet  isi  scopus 10
95. V. S. Atabekyan, L. D. Beklemishev, V. S. Guba, I. G. Lysenok, A. A. Razborov, A. L. Semenov, “Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian”, Russian Math. Surveys, 76:1 (2021), 1–27  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus
96. V. S. Atabekyan, L. D. Beklemishev, V. M. Buchstaber, S. S. Goncharov, V. S. Guba, Yu. L. Ershov, V. V. Kozlov, I. G. Lysenok, S. P. Novikov, Yu. S. Osipov, M. R. Pentus, V. V. Podolskii, A. A. Razborov, V. A. Sadovnichii, A. L. Semenov, A. L. Talambutsa, D. V. Treschev, L. N. Shevrin, “Sergei Ivanovich Adian (obituary)”, Russian Math. Surveys, 76:1 (2021), 177–181  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi
97. Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov, “Clique is hard on average for regular resolution”, Journal of the ACM, 68:4 (2021), 23, 26 pp.  mathnet  crossref  isi 1
98. L. N. Coregliano, A. A. Razborov, Biregularity in Sidorenkos Conjecture, 2021, 31 pp., arXiv: 2108.06599
99. A. A. Razborov, “Pervoprokhodtsy teoreticheskoi informatiki”, Troitskii variant, Mart 2021, 1-3 https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/
100. Igor Lysenok, Alexander Ushakov, “Orientable quadratic equations in free metabelian groups”, J. Algebra, 581 (2021), 303–326  mathnet  crossref  mathscinet  isi  scopus 7
101. L. Babai, K. A. Hansen, V. V. Podolskii, Xiaoming Sun, “Weights of exact threshold functions”, Izv. Math., 85:6 (2021), 1039–1059  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  scopus
102. M. N. Vyalyi, V. V. Podolskii, A. A. Rubtsov, D. A. Shvarts, A. Shen, Lektsii po diskretnoi matematike, Izdatelskii dom Vysshei Shkoly Ekonomiki, 2021, 496 pp. https://id.hse.ru/books/429927775.html  crossref 1
103. Fedor Pakhomov, James Walsh, “Reflection ranks and ordinal analysis”, J. Symb. Log., 86:4 (2021), 1350–1384, arXiv: 1805.02095  mathnet  crossref  mathscinet  isi  scopus 10
104. Fedor Pakhomov and James Walsh, Reflection ranks via infinitary derivations, 2021, 11 pp., arXiv: 2107.03521
105. Yury Savateev, Daniyar Shamkanov, “Non-well-founded proofs for the Grzegorczyk modal logic”, Rev. Symb. Log., 14:1 (2021), 22–50  mathnet  crossref  mathscinet  isi  scopus 11
106. Stanislav O. Speranski, “Negation as a modality in a quantified setting”, Journal of Logic and Computation, 31:5 (2021), 1330–1355  mathnet  crossref  mathscinet  zmath  isi  elib  scopus 6

   2022
107. S. O. Speranski, “Modal bilattice logic and its extensions”, Algebra and Logic, 60:6 (2022), 407–424  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  scopus

   2021
108. Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “The multiplicative-additive Lambek calculus with subexponential and bracket modalities”, J. Logic Lang. Inf., 30:1 (2021), 31–88  mathnet  crossref  mathscinet  zmath  isi  scopus 6
109. Stepan Kuznetsov, “Action logic is undecidable”, ACM Trans. Comput. Log., 22:2 (2021), 10, 26 pp., arXiv: 1912.11273  mathnet  crossref  mathscinet  isi  scopus 13
110. Stepan L. Kuznetsov, “Complexity of a fragment of infinitary action logic with exponential via non-well-founded proofs”, Automated Reasoning with Analytic Tableaux and Related Methods, 30th International Conference, TABLEAUX 2021, Birmingham, UK, September 6–9, 2021, Lecture Notes in Comput. Sci., 12842, Springer, Cham, 2021, 317–334  mathnet  crossref  mathscinet  zmath  isi  scopus 3
111. Stepan L. Kuznetsov, “Relational models for the Lambek calculus with intersection and unit”, Relational and Algebraic Methods in Computer Science. RAMiCS 2021, Marseille, November 2–5, 2021, Lecture Notes in Comput. Sci., 13027, Springer, Cham, 2021, 258–274  mathnet  crossref  mathscinet  zmath  isi  scopus 1
112. S. L. Kuznetsov, “Kleene star, subexponentials without contraction, and infinite computations”, Sib. elektron. matem. izv., 18:2 (2021), 905–922  mathnet  crossref  mathscinet  zmath  isi  scopus 2
113. 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  mathnet  crossref  crossref  mathscinet  zmath  isi  scopus
114. S. L. Kuznetsov, “Printsip dekompozitsii i algoritmicheskaya nerazreshimost dlya monoidov Klini s deleniyami”, Vserossiiskaya nauchnaya konferentsiya “Matematicheskie osnovy informatiki i informatsionno-kommunikatsionnykh sistem”. Sbornik trudov (Tver, 3–8 dekabrya 2021 g.), eds. S. M. Dudakov, B. N. Karlov, TvGU, Tver, 2021, 176–180  crossref
115. Stepan Kuznetsov, “Complexity of the infinitary Lambek calculus with Kleene star”, Rev. Symb. Log., 14:4 (2021), 946–972  mathnet  crossref  mathscinet  zmath  isi  scopus 6

   2020
116. L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020, 84 pp., arXiv: 2012.11773
117. A. Razborov, Kvant, 2020, no. 10, 7–16  mathnet  crossref
118. L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus
119. Nathan Mull, Shuo Pang, Alexander Razborov, “On CDCL-Based Proof Systems with the Ordered Decision Strategy”, Theory and Applications of Satisfiability Testing – SAT 2020, International Conference on Theory and Applications of Satisfiability Testing, Lecture Notes in Comput. Sci., 12178, Springer, Cham, 2020, 149–165  mathnet  crossref  isi  scopus; 2
120. S. I. Adian, V. M. Buchstaber, E. I. Zelmanov, S. V. Kislyakov, V. V. Kozlov, Yu. V. Matiyasevich, S. P. Novikov, D. O. Orlov, A. N. Parshin, V. L. Popov, D. V. Treschev, “Vladimir Petrovich Platonov (on his 80th birthday)”, Russian Math. Surveys, 75:2 (2020), 387–391  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi
121. S. I. Adian, V. S. Atabekyan, “Normal Automorphisms of Free Groups of Infinitely Based Varieties”, Math. Notes, 108:2 (2020), 149–154  mathnet  crossref  crossref  mathscinet  isi  elib  scopus
122. Alexander Kolpakov, Alexey Talambutsa, “Spherical and geodesic growth rates of right-angled Coxeter and Artin groups are Perron numbers”, Discrete Math., 343:3 (2020), 111763, 8 pp., arXiv: 1809.09591  mathnet  crossref  mathscinet  zmath  isi  scopus 2
123. A. Talambutsa, “On subquadratic derivational complexity of semi-Thue systems”, CSR 2020: Computer Science – Theory and Applications, 15th International Computer Science Symposium in Russia, Yekaterinburg, Russian Federation, 29 June 2020 - 3 July 2020, Lecture Notes in Comput. Sci., 12159, Springer, 2020, 379–392  mathnet  crossref  mathscinet  scopus 1
124. Fedor V. Fomin, Vladimir V. Podolskii, “CSR 2018 Special Issue on TOCS”, Theory Comput. Syst., 64 (2020), 1–2  mathnet  crossref  mathscinet  zmath  isi  scopus
125. Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii, Michael Zakharyaschev, “A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom”, Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, IJCAI Organization, 2020, 403–413  crossref  isi 3
126. Alexander Kozachinskiy, Vladimir Podolski, “Multiparty Karchmer – Wigderson Games and Threshold Circuits”, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany, Leibniz Internat. Proc. in Inform., 169, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, 24, 23 pp.  mathnet  crossref  scopus
127. Anastasiya Chistopolskaya, Vladimir V. Podolskii, “On the Decision Tree Complexity of Threshold Functions”, Computer Science - Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 - July 3, 2020, Lecture Notes in Comput. Sci., 12159, Springer, Cham, 2020, 198–210  mathnet  crossref  scopus
128. Dima Grigoriev, Vladimir V. Podolskii, “Tropical Combinatorial Nullstellensatz and sparse polynomials”, Found. Comput. Math., 20 (2020), 753–781  mathnet  crossref  mathscinet  isi  scopus 7
129. Vladimir V. Podolskii, Alexander A. Sherstov, “Inner Product and Set Disjointness: Beyond Logarithmically Many Parties”, ACM Trans. Comput. Theory, 12:4 (2020), 26, 28 pp.  mathnet  crossref  isi  scopus 1
130. A. Freund, F. Pakhomov, “Short proofs for slow consistency”, Notre Dame J. Formal Logic, 61:1 (2020), 31–49, arXiv: 1712.03251  mathnet  crossref  mathscinet  isi  scopus 2
131. Fedor Pakhomov, Alexander Zapryagaev, “Multi-dimensional Interpretations of Presburger Arithmetic in Itself”, J. Logic Comput., 30:8 (2020), 1681–1693, arXiv: 2004.03404  mathnet  crossref  mathscinet  isi  scopus 4
132. Daniyar Shamkanov, “Global neighbourhood completeness of the provability logic GLP”, Advances in Modal Logic (Helsinki, Finland, August 24–28, 2020), Advances in Modal Logic, 13, eds. Nicola Olivetti, Rineke Verbrugge, Sara Negri and Gabriel Sandu, College Publications, London, 2020, 581–596
133. Daniyar Shamkanov, “Non-well-founded derivations in the Gödel-Löb provability logic”, Rev. Symb. Log., 13:4 (2020), 776–796  mathnet  crossref  mathscinet  isi  scopus 2
134. Sergei P. Odintsov, Stanislav O. Speranski, “Belnap–Dunn modal logics: truth constants vs. truth values”, Review of Symbolic Logic, 13:2 (2020), 416–435  mathnet  crossref  mathscinet  zmath  isi  elib  scopus 12
135. Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Reconciling Lambek's restriction, cut-elimination, and substitution in the presence of exponential modalities”, J. Logic Comput., 30:1 (2020), 239–256  mathnet  crossref  mathscinet  zmath  isi  scopus 6
136. S. L. Kuznetsov, N. S. Ryzhkova, “A restricted fragment of the Lambek calculus with iteration and intersection operations”, Algebra and Logic, 59:2 (2020), 129–146  mathnet  crossref  crossref  mathscinet  zmath  isi  scopus
137. Max Kanovich, Stepan Kuznetsov, Vivek Nigam, Andre Scedrov, “Soft subexponentials and multiplexing”, Automated Reasoning, 10th International Conference, IJCAR 2020, Paris, France, July 1–4, 2020, Lecture Notes in Comput. Sci., 12166, Springer, 2020, 500–517  mathnet  crossref  mathscinet  zmath  isi  scopus 5
138. Stepan Kuznetsov, “The ‘long rule’ in the Lambek calculus with iteration: undecidability without meets and joins”, AiML 2020, Helsinki, Finland, August 24–28, 2020, Advances in Modal Logic, 13, College Publications, London, 2020, 425–440  mathnet  mathscinet  zmath  scopus 1
139. Stepan L. Kuznetsov, “A $\Pi^0_1$-bounded fragment of infinitary action logic with exponential”, Logic, Language, and Security: Scedrov Festschrift, Lecture Notes in Comput. Sci., 12300, Springer, Cham, 2020, 3–16  mathnet  crossref  mathscinet  zmath  scopus 1
140. Stepan Kuznetsov, “Complexity of commutative infinitary action logic”, Dynamic Logic. New Trends and Applications, Third International Workshop, DaLi 2020, Prague, Czech Republic, October 9–10, 2020, Lecture Notes in Comput. Sci., 12569, Springer, Cham, 2020, 155–169  mathnet  crossref  mathscinet  zmath  scopus 2
141. S. Kuznetsov, Kvant, 2020, no. 10, 32–33  mathnet
Home page

© Steklov Mathematical Institute of RAS, 2004–2026