Публикации сотрудников за последние годы
|
|
| 1. |
В. С. Атабекян, Л. Д. Беклемишев, В. С. Губа, И. Г. Лысёнок, А. А. Разборов, А. Л. Семёнов, “Научное наследие Сергея Ивановича Адяна в области алгебры и математической логики”, УМН (в печати)  |
|
 2021 |
| 2. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Language models for some extensions of the Lambek calculus”, Inform. and Comput., 2021 (to appear) |
| 3. |
Stepan Kuznetsov, “Action logic is undecidable”, ACM Trans. Comput. Logic, 2021 (to appear) |
|
| 2020 |
| 4. |
Dhruv Mubayi, Alexander Razborov, “Polynomial to exponential transition in Ramsey theory”, Proc. London Math. Soc., 122:1 (2020), 69-92    ; (Published online) |
| 5. |
Л. Н. Корельяно, А. А. Разборов, “Семантические пределы плотных комбинаторных объектов”, УМН, 75:4(454) (2020), 45–152 , arXiv: 1910.08797  [Л. Н. Корельяно, A. A. Razborov, Uspekhi Mat. Nauk ] |
| 6. |
Alexander Razborov, An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs, 2020 , 34 pp., arXiv: 2006.01937 |
| 7. |
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 ; |
| 8. |
L. Coregliano, A. Razborov, Natural Quasirandom Properties, 2020 , 84 pp., arXiv: 2012.11773 |
| 9. |
А. Разборов, “Чувствительность булевых
функций”, Квант, 2020, № 10, 7–16 |
| 10. |
С. И. Адян, В. М. Бухштабер, Е. И. Зельманов, С. В. Кисляков, В. В. Козлов, Ю. В. Матиясевич, С. П. Новиков, Д. О. Орлов, А. Н. Паршин, В. Л. Попов, Д. В. Трещев, “Владимир Петрович Платонов (к восьмидесятилетию со дня рождения)”, УМН, 75:2(452) (2020), 197–200 ; 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 |
| 11. |
С. И. Адян, В. С. Атабекян, “О нормальных автоморфизмах свободных групп бесконечно базируемых многообразий”, Матем. заметки, 108:2 (2020), 163–170 (цит.: 1) ; S. I. Adian, V. S. Atabekyan, “Normal Automorphisms of Free Groups of Infinitely Based Varieties”, Math. Notes, 108:2 (2020), 149–154  |
| 12. |
Л. Д. Беклемишев, А. В. Васильев, Е. П. Вдовин, С. С. Гончаров, В. В. Козлов, П. С. Колесников, В. Д. Мазуров, Ю. В. Матиясевич, А. С. Морозов, А. Н. Паршин, В. Г. Пузаренко, М. В. Швидефски, “Юрий Леонидович Ершов (к восьмидесятилетию со дня рождения)”, УМН, 75:3(453) (2020), 191–194 ; L. D. Beklemishev, A. V. Vasil'ev, E. P. Vdovin, S. S. Goncharov, V. V. Kozlov, P. S. Kolesnikov, V. D. Mazurov, Yu. V. Matiyasevich, A. S. Morozov, A. N. Parshin, V. G. Puzarenko, M. V. Schwidefsky, “Yurii Leonidovich Ershov (on his 80th birthday)”, Russian Math. Surveys, 75:3 (2020), 581–585 |
| 13. |
L. Beklemishev, A. Dmitrieva, J. Makowsky, Axiomatizing Origami planes, 2020 , 25 pp., arXiv: 2012.03250 |
| 14. |
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  ; |
| 15. |
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 ; |
| 16. |
Fedor V. Fomin, Vladimir V. Podolskii, “CSR 2018 Special Issue on TOCS”, Theory Comput. Syst., 64 (2020), 1–2 ; |
| 17. |
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 |
| 18. |
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. ; |
| 19. |
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 ; |
| 20. |
Dima Grigoriev, Vladimir V. Podolskii, “Tropical Combinatorial Nullstellensatz and sparse polynomials”, Found. Comput. Math., 20 (2020), 753–781 ; |
| 21. |
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. ; |
| 22. |
A. Freund, F. Pakhomov, “Short proofs for slow consistency”, Notre Dame J. Formal Logic, 61:1 (2020), 31–49 , arXiv: 1712.03251 (cited: 1) (cited: 1); |
| 23. |
Fedor Pakhomov, James Walsh, “Reflection ranks and ordinal analysis”, J. Symb. Log., 2020, 1–34 (Published online) , arXiv: 1805.02095 ; (Published online) |
| 24. |
Fedor Pakhomov, Alexander Zapryagaev, “Multi-dimensional Interpretations of Presburger Arithmetic in Itself”, J. Logic Comput., 30:8 (2020), 1681–1693 , arXiv: 2004.03404 ; |
| 25. |
Yury Savateev, Daniyar Shamkanov, “Non-well-founded proofs for the Grzegorczyk modal logic”, Rev. Symb. Log., 2020, 1–29 (Published online) ; (Published online) |
| 26. |
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 |
| 27. |
Daniyar Shamkanov, “Non-well-founded derivations in the Gödel-Löb provability logic”, Rev. Symb. Log., 13:4 (2020), 776–796 ; |
| 28. |
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 (cited: 1) (cited: 2) |
| 29. |
С. Л. Кузнецов, Н. С. Рыжкова, “Ограниченный фрагмент исчисления Ламбека с операциями итерации и пересечения”, Алгебра и логика, 59:2 (2020), 190–214 ; 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 (cited: 1) |
| 30. |
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 |
| 31. |
Stepan Kuznetsov, “Complexity of the infinitary Lambek calculus with Kleene star”, Rev. Symb. Log., 2020, 1–28 (Published online) , arXiv: 2005.00404 |
| 32. |
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–449 |
| 33. |
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 ; |
| 34. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “The multiplicative-additive Lambek calculus with subexponential and bracket modalities”, J. Logic Lang. Inf., 2020, 1–58 (Published online) (cited: 1) ; (Published online) |
| 35. |
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 ; |
| 36. |
С. Кузнецов, “Как проверить число на простоту?”, Квант, 2020, № 10, 32–33 |
|
| 2019 |
| 37. |
А. А. Разборов, “Теория сложности”, Математическая составляющая, 2-е изд., расш. и доп., ред. Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин, Математические этюды, М., 2019, 262 https://book.etudes.ru/toc/complexity/ |
| 38. |
С. И. Адян, Н. Н. Андреев, Л. Д. Беклемишев, С. С. Гончаров, Ю. Л. Ершов, Ю. В. Матиясевич, Ю. С. Осипов, М. Р. Пентус, В. А. Плунгян, Е. В. Рахилина, В. А. Садовничий, А. Л. Семёнов, С. Г. Татевосов, В. М. Тихомиров, А. Х. Шень, “Владимир Андреевич Успенский (27.11.1930–27.06.2018)”, УМН, 74:4(448) (2019), 165–180  ; S. I. Adian, N. N. Andreev, L. D. Beklemishev, S. S. Goncharov, Yu. L. Ershov, Yu. V. Matiyasevich, Yu. S. Osipov, M. R. Pentus, V. A. Plungyan, E. V. Rakhilina, V. A. Sadovnichii, A. L. Semenov, S. G. Tatevosov, V. M. Tikhomirov, A. Kh. Shen, “Vladimir Andreevich Uspensky (27/11/1930–27/6/2018)”, Russian Math. Surveys, 74:4 (2019), 735–753 |
| 39. |
С. И. Адян, В. С. Атабекян, “$n$-торсионные группы”, Известия НАН РА Математика, 2019, № 6, 3–18 ; S. I. Adian, V. S. Atabekyan, “$n$-torsion Groups”, J. Contemp. Math. Anal., Armen. Acad. Sci., 54:6 (2019), 319–327 |
| 40. |
Lev D. Beklemishev, Fedor N. Pakhomov, Reflection algebras and conservation results for theories of iterated truth, 2019 , 48 pp., arXiv: 1908.10302 |
| 41. |
E. A. Kolmakov, L. D. Beklemishev, “Axiomatization of provable $n$-provability”, J. Symb. Log., 84:2 (2019), 849–869 (cited: 1) (cited: 1) |
| 42. |
В. А. Александров, Л. Д. Беклемишев, В. М. Бухштабер, А. Ю. Веснин, А. А. Гайфуллин, Н. П. Долбилин, Н. Ю. Ероховец, М. Д. Ковалев, В. С. Макаров, С. П. Новиков, Д. О. Орлов, А. Н. Паршин, И. Х. Сабитов, Д. В. Трещев, О. К. Шейнман, Е. В. Щепин, “Михаил Иванович Штогрин (к восьмидесятилетию со дня рождения)”, УМН, 74:6(450) (2019), 194–197 ; V. A. Alexandrov, L. D. Beklemishev, V. M. Buchstaber, A. Yu. Vesnin, A. A. Gaifullin, N. P. Dolbilin, N. Yu. Erokhovets, M. D. Kovalev, V. S. Makarov, S. P. Novikov, D. O. Orlov, A. N. Parshin, I. Kh. Sabitov, D. V. Treschev, O. K. Sheinman, E. V. Shchepin, “Mikhail Ivanovich Shtogrin (on his 80th birthday)”, Russian Math. Surveys, 74:6 (2019), 1159–1162 |
| 43. |
Л.Д. Беклемишев, “Математика и логика”, Математическая составляющая, ред. Н.Н. Андреев, С.П. Коновалов и Н.А. Панюнин, 2019, 242–261 book.etudes.ru/toc/mathnlogic/ |
| 44. |
A. Kolpakov, A. Talambutsa, Growth rates of Coxeter groups and Perron numbers, 2019 , 19 pp., arXiv: 1912.05608 |
| 45. |
Alexander S. Kulikov, Vladimir V. Podolskii, “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”, Theory Comput. Syst., 63:5 (2019), 956–986 |
| 46. |
A. S. Kulikov, I. Mikhailin, A. Mokhov, V. V. Podolskii, “Complexity of Linear Operators”, 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai University of Finance and Economics, in ShanghaiShanghai; China; 8 December 2019 – 11 December 2019, Leibniz Internat. Proc. in Inform., 149, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019, 17, 1–12 ; |
| 47. |
Luka Mikec, Fedor Pakhomov, Mladen Vuković, “Complexity of the interpretability logic IL”, Log. J. IGPL, 27:1 (2019), 1–7 , arXiv: 1710.05599 |
| 48. |
Fedor Pakhomov, Albert Visser, “On a question of Krajewski's”, J. Symb. Log., 84:1 (2019), 343–358 , arXiv: 1712.01713 (cited: 1) (cited: 1) |
| 49. |
Ali Enayat, Fedor Pakhomov, “Truth, disjunction, and induction”, Arch. Math. Logic, 58 (2019), 753–766 , arXiv: 1805.09890 (cited: 1) |
| 50. |
F. Pakhomov, A weak set theory that proves its own consistency, 2019 , 25 pp., arXiv: 1907.00877 |
| 51. |
Yury Savateev, Daniyar Shamkanov, “Cut Elimination for the Weak Modal Grzegorczyk Logic via Non-well-Founded Proofs”, WoLLIC 2019: Logic, Language, Information, and Computation (International Workshop on Logic, Language, Information, and Computation), Lecture Notes in Comput. Sci., 11541, Springer, Berlin, Heidelberg, 2019, 569–583 |
| 52. |
Max Kanovich, Stepan Kuznetsov, Vivek Nigam, Andre Scedrov, “Subexponentials in non-commutative linear logic”, Math. Structures Comput. Sci., 29:8, A special issue on structural proof theory, automated reasoning and computation in celebration of Dale Miller’s 60th birthday (2019), 1217–1249 , arXiv: 1709.03607 (cited: 5) (cited: 8) |
| 53. |
Stepan Kuznetsov, Valentina Lugovaya, Anastasiia Ryzhova, “Craig’s trick and a non-sequential system for the Lambek calculus and its fragments”, Log. J. IGPL, 27:3 (2019), 252–266 (cited: 1) (cited: 1) |
| 54. |
Stepan Kuznetsov, “The logic of action lattices is undecidable”, Proc. 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019 (Vancouver, B.C., June 24–27, 2019), IEEE, 2019, 1–9 (cited: 1) (cited: 5) |
| 55. |
С. Кузнецов, “Еще раз о полуправильных многогранниках”, Квант, 2019, № 3, 29–31 |
| 56. |
Stepan Kuznetsov, “Complexity of reasoning in residuated Kleene algebras”, 5th International Workshop on Structures and Deduction (Dortmund, June 29–30, 2019), 2019 http://www.anupamdas.com/sd19/papers/SD19_paper_9.pdf |
| 57. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “The complexity of multiplicative-additive Lambek calculus: 25 years later”, WoLLIC 2019: Logic, Language, Information, and Computation, International Workshop on Logic, Language, Information, and Computation (Utrecht, July 2–5, 2019), Lecture Notes in Comput. Sci., 11541, Springer, Berlin, Heidelberg, 2019, 356–372 (cited: 2) |
| 58. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “L-models and R-models for Lambek calculus enriched with additives and the multiplicative unit”, WoLLIC 2019: Logic, Language, Information, and Computation, International Workshop on Logic, Language, Information, and Computation (Utrecht, July 2–5, 2019), Lecture Notes in Comput. Sci., 11541, Springer, Berlin, Heidelberg, 2019, 373–391 (cited: 2) |
| 59. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Undecidability of a Newly Proposed Calculus for CatLog3”, Formal Grammar, 24th International Conference, FG 2019, Riga, Latvia, August 11, 2019, Lecture Notes in Comput. Sci., 11668, Springer, Berlin, Heidelberg, 2019, 67–83 (cited: 1) |
| 60. |
Stepan Kuznetsov, “Half a way towards circular proofs for Kleene lattices”, Circularity in Syntax and Semantics (Gothenburg, November 20–22, 2019), University of Gothenburg, Gothenburg, 2019, 42–45 http://www.cse.chalmers.se/~bahafs/CiSS2019/CiSS2019BoA.pdf |
| 61. |
С. Кузнецов, “Египетские дроби”, Квант, 2019, № 12, 10–11 |
|
| 2018 |
| 62. |
Alexander Razborov, “On Space and Depth in Resolution”, Computational Complexity, 27:3 (2018), 511-559 (cited: 3) (cited: 4) |
| 63. |
Albert Atserias, Ilario Bonacina, Susanna de Rezende, Massimo Lauria, Jakob Nordström, Alexander Razborov, “Clique Is Hard on Average for Regular Resolution”, Journal version to appear in “Journal of the ACM”, Proceedings of the 50th ACM Symposium on Theory of Computing (Los Angeles, CA, USA, June 2018), ACM Press, 2018, 866-877 (cited: 3) |
| 64. |
И. Г. Лысëнок, “Подход к изучению конечно определенных групп, основанный на понятии дискретной кривизны”, Матем. заметки, 103:4 (2018), 568–575 ; I. G. Lysenok, “An Approach to the Study of Finitely Presented Groups Based on the Notion of Discrete Curvature”, Math. Notes, 103:4 (2018), 610–615 (cited: 1) |
| 65. |
С. И. Адян, “Об исследованиях Геннадия Семёновича Маканина по алгоритмическим вопросам теории групп и полугрупп”, УМН, 73:3(441) (2018), 183–196 ; S. I. Adian, “On the studies of Gennadii Semënovich Makanin on algorithmic questions of the theory of groups and semigroups”, Russian Math. Surveys, 73:3 (2018), 553–568 |
| 66. |
С. И. Адян, В. С. Атабекян, “Центральные расширения свободных периодических групп”, Матем. сб., 209:12 (2018), 3–16 (цит.: 3) (цит.: 4) ; S. I. Adian, V. S. Atabekyan, “Central extensions of free periodic groups”, Sb. Math., 209:12 (2018), 1677–1689 (cited: 4) (cited: 3) |
| 67. |
Lev Beklemishev, “A note on strictly positive logics and word rewriting systems”, Larisa Maximova on Implication, Interpolation, and Definability, Outst. Contrib. Log., 15, eds. Sergei Odintsov, Springer, Berlin, Heidelberg, 2018, 61–70 (cited: 3) (cited: 5) |
| 68. |
Л. Д. Беклемишев, “Исчисление для схем рефлексии и спектры консервативности”, УМН, 73:4(442) (2018), 3–52 ; L. D. Beklemishev, “Reflection calculus and conservativity spectra”, Russian Math. Surveys, 73:4 (2018), 569–613 (cited: 1) |
| 69. |
Lev D. Beklemishev, “A universal algebra for the variable-free fragment of $RC^\nabla$”, Logical Foundations of Computer Science, International Symposium, LFCS 2018, Lecture Notes in Comput. Sci., 10703, Springer, Berlin, Heidelberg, 2018, 91–106 (cited: 2) (cited: 3) |
| 70. |
Gerald Berger, L. D. Beklemishev, Hans Tompits, “A many-sorted variant of Japaridze's polymodal provability logic”, Log. J. IGPL, 26:5 (2018), 505–538 |
| 71. |
L. D. Beklemishev, A universal Kripke frame for the variable-free fragment of $RC^\nabla$, 2018 , 5 pp., arXiv: 1804.02641 |
| 72. |
Е. А. Колмаков, Л. Д. Беклемишев, “Аксиоматизация доказуемой $n$-доказуемости”, Докл. РАН, 483:3 (2018), 244–248 ; E. A. Kolmakov, L. D. Beklemishev, “Axiomatizing provable $n$-provability”, Dokl. Math., 98:3 (2018), 582–585 |
| 73. |
Tobias Hartnick, Alexey Talambutsa, “Relations between counting functions on free groups and free monoids”, Groups, Geometry and Dynamics, 12:4 (2018), 1485–1521 , arXiv: 1508.03166 (cited: 1) |
| 74. |
Dima Grigoriev, Vladimir V. Podolskii, “Tropical effective primary and dual nullstellensätze”, Discrete Comput. Geom., 59:3 (2018), 507–552 (cited: 2) (cited: 3) |
| 75. |
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev, “Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity”, Journal of the ACM, 65:5 (2018), 28 , 51 pp. (cited: 5) (cited: 11) |
| 76. |
Fedor V. Fomin, Vladimir V. Podolskii (eds.), Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings, Lecture Notes in Computer Science 10846, Springer, 2018 https://link.springer.com/book/10.1007 |
| 77. |
Alexander Zapryagaev, Fedor Pakhomov, “Interpretations of Presburger Arithmetic in Itself”, International Symposium on Logical Foundations of Computer Science (Deerfield Beach, FL, USA, January 8–11, 2018), Lecture Notes in Comput. Sci., 10703, Springer, 2018, 354–367 , arXiv: 1709.07341 |
| 78. |
Y. Savateev, D. Shamkanov, Cut Elimination for Weak Modal Grzegorczyk Logic via Non-Well-Founded Proofs, 2018 , 17 pp., arXiv: 1804.01432 |
| 79. |
Y. Savateev, D. Shamkanov, Non-Well-Founded Proofs for the Grzegorczyk Modal Logic, 2018 , 31 pp., arXiv: 1804.00955 |
| 80. |
Glyn Morrill, Stepan Kuznetsov, Max Kanovich, Andre Scedrov, “Bracket induction for the Lambek calculus with bracket modalities”, Formal Grammar 2018, 23rd International Conference, FG 2018 (Sofia, Bulgaria, August 11–12, 2018), Lecture Notes in Comput. Sci., 10950, Springer-Verlag, Berlin, Heidelberg, 2018, 84–101 (cited: 2) |
| 81. |
Max Kanovich, Stepan Kuznetsov, Vivek Nigam, Andre Scedrov, “A logical framework with commutative and non-commutative subexponentials”, Automated Reasoning, IJCAR 2018 (Oxford, UK, July 14-17, 2018), Lecture Notes in Comput. Sci., 10900, eds. D. Galmiche, S. Schulz, R. Sebastiani, Springer, Cham, 2018, 228–245 (cited: 3) (cited: 6) |
| 82. |
С. Л. Кузнецов, “О полноте фрагмента исчисления Ламбека с операциями итерации и пересечения относительно реляционных моделей”, Мальцевские чтения 2018 (Новосибирск, 19–22 ноября 2018 г.), Институт математики им. С. Л. Соболева СО РАН; Новосибирский гос. университет, Новосибирск, 2018, 224 http://www.math.nsc.ru/conference/malmeet/18/maltsev18.pdf |
| 83. |
С. Кузнецов, “Замощения сферы и архимедовы многогранники”, Квант, 2018, № 11, 9 |
| 84. |
С. Кузнецов, “Задачи помогают друг другу”, Квант, 2018, № 5, 24 |
| 85. |
С. Кузнецов, “Полуправильные замощения плоскости”, Квант, 2018, № 3, 32–33 |
| 86. |
Stepan Kuznetsov, “$*$-continuity vs. induction: divide and conquer”, 12th Conference on ""Advances in Modal Logic"", AiML 2018, Advances in Modal Logic, 12, University of Bern, Bern, Switzerland, 2018, 493–510 (cited: 3); |
|
| 2017 |
| 87. |
Alexander Razborov, “On the width of semi-algebraic proofs and algorithms”, Mathematics of Operation Research, 42:4 (2017), 1106–1134 (cited: 1) (cited: 2) |
| 88. |
Oleg Pikhurko, Alexander Razborov, “Asymptotic structure of graphs with the minimum number of triangles”, Comb. Probab. Comput., 26:1 (2017), 138–160 (cited: 11) (cited: 14) |
| 89. |
L. N. Coregliano, A. A. Razborov, “On the density of transitive tournaments”, J. Graph Theory, 85:1 (2017), 12–21 , arXiv: 1501.04074 (cited: 7) (cited: 8) |
| 90. |
Yuan Li, Alexander Razborov, Benjamin Rossman, “On the $AC^0$ Complexity of Subgraph Isomorphism”, SIAM Journal on Computing, 46:3 (2017), 936–971 (cited: 4) (cited: 5) |
| 91. |
С. И. Адян, В. С. Атабекян, “О свободных группах бесконечно базируемых многообразий С. И. Адяна”, Изв. РАН. Сер. матем., 81:5 (2017), 3–14 (цит.: 6) (цит.: 7) ; S. I. Adian, V. S. Atabekyan, “On free groups in the infinitely based varieties of S. I. Adian”, Izv. Math., 81:5 (2017), 889–900 (cited: 7) (cited: 6) |
| 92. |
С. И. Адян, В. С. Атабекян, “Периодические произведения групп”, Известия НАН РА Математика, 52:3 (2017), 3–15 (цит.: 5); S. I. Adian, V. S. Atabekyan, “Periodic products of groups”, J. Contemp. Math. Anal., Armen. Acad. Sci., 52:3 (2017), 111–117 (cited: 5) (cited: 4) |
| 93. |
Lev D. Beklemishev, Reflection calculus and conservativity spectra, 2017 , 28 pp., arXiv: 1703.09314 |
| 94. |
Л. Д. Беклемишев, “О свойстве редукции для $GLP$-алгебр”, Докл. РАН, 472:4 (2017), 378–382 (цит.: 1) (цит.: 3) ; L. D. Beklemishev, “On the Reduction Property for GLP-Algebras”, Dokl. Math., 95:1 (2017), 50–54 (cited: 3) (cited: 3) |
| 95. |
Lev D. Beklemishev, “On the reflection calculus with partial conservativity operators”, Lecture Notes in Comput. Sci., 10388, 2017, 48–67 (cited: 5) (cited: 6) |
| 96. |
Lev Beklemishev, “Guest Editorial: Computer Science Symposium in Russia”, Theory Comput. Syst., 61:2 (2017), 462–463 https://link.springer.com/content/pdf/10.1007 |
| 97. |
M. Bucher, A. Talambutsa, “Minimal exponential growth rates of metabelian Baumslag–Solitar groups and lamplighter groups”, Groups, Geometry and Dynamics, 11:1 (2017), 189–209 , arXiv: 1506.03569 (cited: 5) (cited: 5) |
| 98. |
Vladimir V. Podolskii, “Bounds in Ontology-Based Data Access via Circuit Complexity”, Theory Comput. Syst., 61:2 (2017), 464–493 (cited: 1) (cited: 1) |
| 99. |
M. Bienvenu, S. Kikot, R. Kontchakov, V. V. Podolskii, V. Ryzhikov, M. Zakharyaschev, “The complexity of ontology-based data access with OWL2QL and bounded treewidth queries”, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Volume Part F127745, 9 May 2017 (Chicago, United States, 14 May 2017 до 19 May 2017, Код 127745), 2017, 201–216 (цит.: 4) (цит.: 12) |
| 100. |
O. A. Gerasimova, S. P. Kikot, V. V. Podolskii, M. Zakharyaschev, “More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom”, International Conference on Knowledge Engineering and the Semantic Web KESW 2017: Knowledge Engineering and Semantic Web, Commun. Comput. Inf. Sci., 786, Springer, 2017, 143–158 (cited: 1) |
| 101. |
A. S. Kulikov, V. V. Podolskii, “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Leibniz Internat. Proc. in Inform., 66, no. 49, 2017, 1–14 (cited: 3) (cited: 3) |
| 102. |
D. Yu. Grigor'ev, V. V. Podolskii, “Tropical Combinatorial Nullstellensatz and Fewnomials Testing”, International Symposium on Fundamentals of Computation Theory FCT 2017: Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 10472, Springer, 2017, 284–297 (cited: 2) |
| 103. |
O. Gerasimova, S. Kikot, V. Podolskii, M. Zakharyaschev, “On the data complexity of ontology-mediated queries with a covering axiom”, Proceedings of the 30th International Workshop on Description Logics (Montpellier, France, 18 July 2017 - 21 July 2017), CEUR Workshop Proceedings, 1879, CEUR-WS, 2017, 39 , 12 pp. (cited: 2) |
| 104. |
Fedor Pakhomov, “Solovay’s completeness without fixed points”, Logic, Language, Information, and Computation, 24th International Workshop, WoLLIC 2017 (London, UK, July 18-21, 2017), Lecture Notes in Comput. Sci., 10388, eds. Kennedy J., de Queiroz R., Springer, Berlin, 2017, 281–294 arxiv: 1703.10262 (cited: 1) (cited: 1) |
| 105. |
Yury Savateev, Daniyar Shamkanov, “Cut-elimination for the modal Grzegorczyk logic via non-well-founded proofs”, Logic, Language, Information, and Computation, 24th International Workshop, WoLLIC 2017 (London, UK, July 18-21, 2017), Lecture Notes in Comput. Sci., 10388, eds. Juliette Kennedy and Ruy de Queiroz, Springer, 2017, 321–336 (cited: 1) (cited: 3) |
| 106. |
Daniyar Shamkanov, “Global neighbourhood completeness of the Gödel-Löb provability logic”, Logic, Language, Information, and Computation, 24th International Workshop, WoLLIC 2017 (London, UK, July 18-21, 2017), Lecture Notes in Comput. Sci., 10388, eds. Juliette Kennedy and Ruy de Queiroz, Springer, 2017, 358–371 (cited: 1) (cited: 1) |
| 107. |
S. Kuznetsov, A. Okhotin, “Conjunctive categorial grammars”, Proceedings of the 15th Meeting on the Mathematics of Language (London, July 13–14, 2017), ACL Anthology, 2017, 140–151 (W17-3414) http://aclweb.org/anthology/W17-3414 |
| 108. |
S. Kuznetsov, G. Morrill, O. Valentín, “Count-invariance including exponentials”, Proceedings of the 15th Meeting on the Mathematics of Language (London, July 13–14, 2017), ACL Anthology, 2017, 128–139 (W17-3413) http://www.aclweb.org/anthology/W17-3413 |
| 109. |
Stepan Kuznetsov, “The Lambek calculus with iteration: two variants”, WoLLIC 2017 (London, July 18–21, 2017), Lecture Notes in Comput. Sci., 10388, 2017, 182–198 (cited: 2) (cited: 6) |
| 110. |
С. Кузнецов, “Птичка вылетает!”, Квантик, 2017, № 2, 10–11 |
| 111. |
Max Kanovich, Stepan Kuznetsov, Glyn Morrill, Andre Scedrov, “A polynomial-time algorithm for the Lambek calculus with brackets of bounded order”, 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017) (Oxford, September 3–9, 2017), Leibniz Internat. Proc. in Inform., 84, eds. D. Miller, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2017, 22:1–22:17 (cited: 4) |
| 112. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Undecidability of the Lambek calculus with subexponential and bracket modalities”, Fundamentals of Computation Theory, FCT 2017 (Bordeaux, September 11–13, 2017), Lecture Notes in Comput. Sci., 10472, eds. R. Klasing, M. Zeitoun, Springer, 2017, 326–340 (cited: 6) |
| 113. |
S. Kuznetsov, Eliminating the unit constant in the Lambek calculus with brackets, 2017 , 7 pp., arXiv: 1711.06361 |
| 114. |
С. Кузнецов, “Теорема Шаля в трех лицах (окончание)”, Квант, 2017, № 10, 2–5 |
| 115. |
С. Кузнецов, “Теорема Шаля в трех лицах”, Квант, 2017, № 9, 10–14 |
| 116. |
С. Кузнецов, “Знание — сила!”, Квант, 2017, № 6, 21–24 |
| 117. |
С. Кузнецов, “Расстояния на сфере”, Квант, 2017, № 4, 36–38 |
| 118. |
С. Кузнецов, “Птичка вылетает!”, Квант, 2017, № 1, 30–31 |
|
| 2016 |
| 119. |
Alexander Razborov, “A new kind of tradeoffs in propositional proof complexity”, Journal of the ACM, 63:2 (2016), 16 , 14 pp. (cited: 10) (cited: 13) |
| 120. |
Igor Lysenok, Alexander Ushakov, “Spherical quadratic equations in free metabelian groups”, Proc. Amer. Math. Soc., 144:4 (2016), 1383–1390 , arXiv: 1304.4898 (cited: 2) |
| 121. |
Igor Lysenok, Alexei Miasnikov, Alexander Ushakov, “Quadratic equations in the Grigorchuk group”, Groups Geom. Dyn., 10:1 (2016), 201–239 , arXiv: 1304.5579 (cited: 3) |
| 122. |
С. И. Адян, В. С. Атабекян, “$C^*$-простота $n$-периодических произведений”, Матем. заметки, 99:5 (2016), 643–648 (цит.: 3) (цит.: 2) ; S. I. Adian, V. S. Atabekyan, “$C^*$-Simplicity of $n$-Periodic Products”, Math. Notes, 99:5 (2016), 631–635 (cited: 2) (cited: 1) |
| 123. |
L. D. Beklemishev, “Proof theoretic analysis by iterated reflection”, Turing's revolution, Part II, Birkhäuser/Springer, Cham, 2016, 225–270 (cited: 1) |
| 124. |
Lev Beklemishev, Tommaso Flaminio, “Franco Montagna's work on provability logic and many-valued logic”, Studia Logica, 104:1 (2016), 1–46 |
| 125. |
L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290 |
| 126. |
Lev Beklemishev, Daniyar Shamkanov, “Some abstract versions of Gödel's second incompleteness theorem based on non-classical logics”, Liber Amicorum Alberti: A tribute to Albert Visser, Tributes, 30, eds. Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten, College Publications, London, 2016, 15–29 url, arXiv: 1602.05728 |
| 127. |
Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857 |
| 128. |
Advances in Modal Logic, v. 11, eds. Lev Beklemishev, Stephane Demri, Andras Mate, College Publications, London, 2016 , xii+570 pp. |
| 129. |
Lev Beklemishev, “Notes on a reduction property of GLP-algebras”, 11th International Conference on Advances in Modal Logic, Short Papers (Budapest, 30 August – 2 September, 2016), 2016, 7–13 |
| 130. |
M. Bucher, A. Talambutsa, “Exponential growth rates of free and amalgamated products”, Israel J. Math., 212:2 (2016), 521–546 , arXiv: 1209.4071 (cited: 4) (cited: 4) |
| 131. |
M. Bienvenu, S. Kikot, R. Kontchakov, V. Podolskii, M. Zakharyaschev, “Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries” (Cape Town, South Africa, 22 April 2016 – 25 April 2016), CEUR Workshop Proceedings, 1577, 2016 , arXiv: 1604.05258 |
| 132. |
Ф. Н. Пахомов, “Линейные $\mathrm{GLP}$-алгебры и их элементарные теории”, Изв. РАН. Сер. матем., 80:6 (2016), 173–216 ; F. N. Pakhomov, “Linear $\mathrm{GLP}$-algebras and their elementary theories”, Izv. Math., 80:6 (2016), 1159–1199 |
| 133. |
Д. С. Шамканов, “Теорема о реализации для логики доказуемости Гëделя–Лëба”, Матем. сб., 207:9 (2016), 171–190 (цит.: 2) (цит.: 2) ; D. S. Shamkanov, “A realization theorem for the Gödel-Löb provability logic”, Sb. Math., 207:9 (2016), 1344–1360 (cited: 2) (cited: 4) |
| 134. |
M. Kanovich, S. Kuznetsov, A. Scedrov, “On Lambek's restriction in the presence of exponential modalities”, Lecture Notes in Comput. Sci., 9537, 2016, 146–158 (cited: 2) (cited: 4) |
| 135. |
Max Kanovich, Stepan Kuznetsov, Andre Scedrov, “Undecidability of the Lambek calculus with a relevant modality”, Lecture Notes in Comput. Sci., 9804, eds. A. Foret, G. Morrill, R. Muskens, R. Osswald, S. Pogodalla, 2016, 240–256 , arXiv: 1601.06303 (cited: 9) |
| 136. |
С. Л. Кузнецов, “О преобразовании грамматик Ламбека с одним делением в контекстно-свободные грамматики”, Современные проблемы математики, механики и математической физики. II, Сборник статей, Тр. МИАН, 294, МАИК, М., 2016, 141–151 (цит.: 2) ; S. L. Kuznetsov, “On translating Lambek grammars with one division into context-free grammars”, Proc. Steklov Inst. Math., 294 (2016), 129–138 (cited: 2) (cited: 4) |
| 137. |
M. Kanovich, S. Kuznetsov, V. Nigam, A. Scedrov, “On the proof theory of non-commutative subexponentials”, Dale Fest!, Seminar in honor of the 60th birthday of Dale Miller (Paris, December 15–16, 2017), Université Paris Diderot, 2016, 10 p. http://www.lsv.fr/~baelde/dale-fest/kanovich-etal.pdf |
|
| 2015 |
| 138. |
A. A. Razborov, “Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution”, Ann. of Math. (2), 181:2 (2015), 415–472 (cited: 3) (cited: 12) (cited: 16) |
| 139. |
С. И. Адян, В. В. Беняш-Кривец, В. М. Бухштабер, Е. И. Зельманов, В. В. Козлов, Г. А. Маргулис, С. П. Новиков, А. Н. Паршин, Г. Прасад, А. С. Рапинчук, Л. Д. Фаддеев, В. И. Черноусов, “Владимир Петрович Платонов (к 75-летию со дня рождения)”, УМН, 70:1(421) (2015), 204–207 ; S. I. Adian, V. V. Benyash-Krivets, V. M. Buchstaber, E. I. Zelmanov, V. V. Kozlov, G. A. Margulis, S. P. Novikov, A. N. Parshin, G. Prasad, A. S. Rapinchuk, L. D. Faddeev, V. I. Chernousov, “Vladimir Petrovich Platonov (on his 75th birthday)”, Russian Math. Surveys, 70:1 (2015), 197–201 (cited: 2) (cited: 5) |
| 140. |
С. И. Адян, “Новые оценки нечетных периодов бесконечных бернсайдовых групп”, Избранные вопросы математики и механики, Сборник статей. К 150-летию со дня рождения академика Владимира Андреевича Стеклова, Тр. МИАН, 289, МАИК, М., 2015, 41–82 (цит.: 12) (цит.: 14) ; S. I. Adian, “New Estimates of Odd Exponents of Infinite Burnside Groups”, Proc. Steklov Inst. Math., 289 (2015), 33–71 (cited: 14) (cited: 3) (cited: 7) |
| 141. |
С. И. Адян, В. С. Атабекян, “Характеристические свойства и равномерная неаменабельность $n$-периодических произведений групп”, Изв. РАН. Сер. матем., 79:6 (2015), 3–17 (цит.: 4) (цит.: 5) (цит.: 1); S. I. Adian, Varuzhan Atabekyan, “Characteristic properties and uniform non-amenability of $n$-periodic products of groups”, Izv. Math., 79:6 (2015), 1097–1110 (cited: 5) |
| 142. |
С. И. Адян, В. В. Беняш-Кривец, В. М. Бухштабер, Е. И. Зельманов, В. В. Козлов, Г. А. Маргулис, С. П. Новиков, А. Н. Паршин, Г. Прасад, А. С. Рапинчук, Л. Д. Фаддеев, В. И. Черноусов, “Владимир Петрович Платонов (к 75-летию со дня рождения)”, Чебышевский сб., 16:4 (2015), 6–10 |
| 143. |
G. S. Makanin, A. Sh. Malkhasyan, “General solution of quadratic equations in free groups”, Proceedings of the Yerevan State University. Physical and Mathematical Sciences., 2015, no. 2, 62–65 |
| 144. |
L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666 |
| 145. |
L. D. Beklemishev, D. V. Musatov (eds.), Computer Science – Theory and Applications, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13–17, 2015, Proceedings, Lecture Notes in Computer Science, 9139, Springer, 2015 , xx+443 pp. |
| 146. |
Л. Д. Беклемишев, А. А. Оноприенко, “О некоторых медленно сходящихся системах преобразований термов”, Матем. сб., 206:9 (2015), 3–20 (цит.: 3) (цит.: 4) ; L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190 (cited: 4) (cited: 4) |
| 147. |
K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Inform. and Comput., 240 (2015), 56–73 (cited: 5) (cited: 2) |
| 148. |
Dima Grigoriev, Vladimir V. Podolskii, “Complexity of tropical and min-plus linear prevarieties”, Comput. Complexity, 24:1 (2015), 31–64 http://www.mpim-bonn.mpg.de/preblob/5202, arXiv: 1204.4578 (цит.: 1) (цит.: 8) (цит.: 11) |
| 149. |
D. Grigoriev, V. V. Podolskii, “Tropical effective primary and dual Nullstellensätze”, 32nd International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., 30, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, 379–391 (цит.: 5) |
| 150. |
V. V. Podolskii, “Circuit complexity meets ontology-based data access”, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13–17, 2015, Proceedings, Lecture Notes in Comput. Sci., 9139, 2015, 7–26 , arXiv: 1506.01296 (cited: 2) |
| 151. |
Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii, “Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results”, 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 2015, 317–328 (cited: 3) (cited: 11) |
| 152. |
Ф. Н. Пахомов, “Об элементарных теориях систем ординальных обозначений на основе схем рефлексии”, Избранные вопросы математики и механики, Сборник статей. К 150-летию со дня рождения академика Владимира Андреевича Стеклова, Тр. МИАН, 289, МАИК, М., 2015, 206–226 (цит.: 4) (цит.: 5) ; F. N. Pakhomov, “On Elementary Theories of Ordinal Notation Systems Based on Reflection Principles”, Proc. Steklov Inst. Math., 289 (2015), 194–212 (cited: 5) (cited: 1) (cited: 5) |
| 153. |
Fedor Pakhomov, Ordinal notations in Caucal hierarchy, 2015 , 15 с., arXiv: 1512.05036 |
| 154. |
Daniyar Shamkanov, “Nested sequents for provability logic GLP”, Log. J. IGPL, 23:5 (2015), 789–815 (cited: 3) (cited: 4) |
| 155. |
С. Л. Кузнецов, “О преобразовании контекстно-свободных грамматик в грамматики Ламбека”, Современные проблемы математики, механики и математической физики, Сборник статей, Тр. МИАН, 290, МАИК, М., 2015, 72–79 (цит.: 1) (цит.: 1) (цит.: 1); S. L. Kuznetsov, “On Translating Context-Free Grammars into Lambek Grammars”, Proc. Steklov Inst. Math., 290 (2015), 63–69 (cited: 1) (cited: 1) (cited: 1) |
| 156. |
С. Л. Кузнецов, Н. С. Рыжкова, “Фрагмент исчисления Ламбека с итерацией”, Мальцевские чтения 2015 (Новосибирск, 3–7 мая 2015 г.), Институт математики им. С.Л. Соболева СО РАН; Новосибирский гос. университет, Новосибирск, 2015, 213 http://www.math.nsc.ru/conference/malmeet/15/malmeet15.pdf |
|
Посмотреть карту
Наверх
Список публикаций
