Home page
Home page
Home page
Russian page
English page
Math-Net.Ru | MMS | Scopus | MathSciNet | Zentralblatt MATH | Web-mail 

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


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

View Map
Transit directions

   

Department of Mathematical Logic

| Seminars | Publications |
Staff
Adian Sergei Ivanovich

Doctor Phys.-Math. Sci., Academician, Head of Department
office: 508; tel.: +7 (499) 941 01 83, +7 (495) 984 81 41 * 36 34; e-mail: sia@mi.ras.ru
Principal fields of research: Algorithmic problems in algebras. Semigroups theory. Groups theory.
Beklemishev Lev Dmitrievich

Doctor Phys.-Math. Sci., Corresponding Member of RAS, Chief Scientific Researcher
office: 515; tel.: +7 (495) 984 81 43, +7 (495) 984 81 41 * 37 44; e-mail: bekl@mi.ras.ru
Principal fields of research: Mathematical logic. Proof theory. Provability logic. Modal logic. Fragments of arithmetic.
Beklemishev Lev Dmitrievich
Kuznetsov Stepan L'vovich

Candidate Phys.-Math. Sci., Scientific Researcher
office: 515; tel.: +7 (495) 984 81 41 * 37 44; e-mail: skuzn@inbox.ru
Lysenok Igor Geront'evich

Doctor Phys.-Math. Sci., Leading Scientific Researcher
office: 507; tel.: +7 (495) 984 81 41 * 37 52; e-mail: lysionok@mi.ras.ru
Principal fields of research: Combinatorial group theory. Algorithmic problems of group theory.
Pakhomov Fedor Nikolaevich

Candidate Phys.-Math. Sci., Scientific Researcher
e-mail: pakhfn@gmail.com
Principal fields of research: Proof theory, modal logic, decision problems.
Podolskii Vladimir Vladimirovich

Candidate Phys.-Math. Sci., Senior Scientific Researcher
office: 506; tel.: +7 (495) 984 81 41 * 37 46; e-mail: podolskii@mi.ras.ru
Personal page: http://www.mi.ras.ru/~podolskii/
Principal fields of research: Computational complexity theory.
Razborov Aleksandr Aleksandrovich

Doctor Phys.-Math. Sci., Corresponding Member of RAS, Chief Scientific Researcher
office: 506; tel.: +7 (495) 984 81 41 * 37 46; e-mail: razborov@mi.ras.ru
Personal page: http://www.mi.ras.ru/~razborov/
Principal fields of research: Complexity of proofs and computations.
Semenov Aleksei L'vovich

Doctor Phys.-Math. Sci., Professor, Academician, Chief Scientific Researcher

Principal fields of research: Mathematical problems of computer science.
Shamkanov Daniyar Salkarbekovich

Candidate Phys.-Math. Sci., Scientific Researcher
office: 515; tel.: +7 (495) 984 81 43; e-mail: daniyar@mi.ras.ru
Principal fields of research: Proof theory. Nonclassical logics. Combinatory logic.
Talambutsa Alexey Leonidovich

Candidate Phys.-Math. Sci., Scientific Researcher
office: 507; tel.: +7 (495) 984 81 41 * 37 52; e-mail: altal@mi.ras.ru
Principal fields of research: Combinatorial group theory. Algorithmic problems for groups and semigroups.

Makanin Gennadii Semenovich

Doctor Phys.-Math. Sci., Out-Of-Staff Member
e-mail: makanin@mi.ras.ru
Principal fields of research: Combinatorial group theory. Algorithmic problems of semigropus theory.
Top
Seminars
Seminar of the Department of Mathematical Logic "Algorithmic problems in algebra and logic"
Seminar Chairman: S. I. Adian
MSU, auditorium 16-04
Seminar of the Department of Mathematical Logic "Proof Theory"
Seminar Chairman: L. D. Beklemishev
Special seminar "Geometric Theory of Groups", 2012
Seminar Chairman: I. G. Lysenok
Steklov Mathematical Institute, Room 430 (8 Gubkina)
Recent publications

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


   2016
1. Alexander Razborov, “A new kind of tradeoffs in propositional proof complexity”, Journal of the ACM, 63:2 (2016), 16 , 14 pp.  mathnet  crossref  isi  scopus
2. Igor Lysenok, Alexander Ushakov, “Spherical quadratic equations in free metabelian groups”, Proc. Amer. Math. Soc., 144:4 (2016), 1383–1390 , arXiv: 1304.4898  mathnet  crossref  mathscinet  isi  scopus
3. Igor Lysenok, Alexei Miasnikov, Alexander Ushakov, “Quadratic equations in the Grigorchuk group”, Groups Geom. Dyn., 10:1 (2016), 201–239 , arXiv: 1304.5579  mathnet  crossref  mathscinet  isi  scopus
4. S. I. Adian, V. S. Atabekyan, “$C^*$-Simplicity of $n$-Periodic Products”, Math. Notes, 99:5 (2016), 631–635  mathnet  crossref  crossref  elib  scopus
5. Lev Beklemishev, Tommaso Flaminio, “Franco Montagna's work on provability logic and many-valued logic”, Studia Logica, 104:1 (2016), 1–46  mathnet  crossref  mathscinet  isi  scopus
6. Lev Beklemishev, Daniyar Shamkanov, Some abstract versions of Gödel's second incompleteness theorem based on non-classical logics, 2016 , 18 pp., arXiv: 1602.05728
7. L. D. Beklemishev, Notes on a reduction property for GLP-algebras, 2016 , 8 pp., arXiv: 1606.00290
8. 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, 20–38 url
9. Gerald Berger, Lev D. Beklemishev, Hans Tompits, A Many-Sorted Variant of Japaridze's Polymodal Provability Logic, 2016 , 15 pp., arXiv: 1601.02857
10. Michelle Bucher, Alexey Talambutsa, “Exponential growth rates of free and amalgamated products”, Israel J. Math., 212:2 (2016), 521–546 , arXiv: 1209.4071  mathnet  crossref  mathscinet  isi (cited: 1 \citnumescopus 1)  scopus
11. M. Bienvenu, S. Kikot, R. Kontchakov, V. Podolskii, M. Zakharyaschev, “Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries”, 29th International Workshop on Description Logics, DL 2016 (Cape Town, South Africa, 22 April 2016 – 25 April 2016), CEUR Workshop Proceedings, 1577, 2016 , arXiv: 1604.05258  mathnet  scopus
12. F. N. Pakhomov, “Linear GLP-algebras and their elementary theories”, Izv. RAN. Ser. Mat., 2016 (to appear)  mathnet
13. D. S. Shamkanov, “A realization theorem for the Gödel–Löb provability logic”, Mat. Sb., 207:9 (2016) (to appear)  mathnet
14. M. Kanovich, S. Kuznetsov, A. Scedrov, “On Lambek's restriction in the presence of exponential modalities”, Logical Foundations of Computer Science 2016, Lecture Notes in Comput. Sci., 9537, Springer, 2016, 146–158  mathnet  crossref  isi  scopus
15. M. Kanovich, S. Kuznetsov, A. Scedrov, Undecidability of the Lambek calculus with a relevant modality, 2016 , 12 pp., arXiv: 1601.06303
16. S. L. Kuznetsov, Modern problems of mathematics, mechanics, and mathematical physics. Part II, Tr. Mat. Inst. Steklova, 294, MAIK Nauka/Interperiodica, Moscow, 2016 (to appear)  mathnet

   2015
17. A. Razborov, “Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution”, Ann. of Math. (2), 181:2 (2015), 415–472  mathnet (cited: 3)  crossref  mathscinet (cited: 3)  zmath  isi (cited: 2)  elib (cited: 2 \citnumescopus 2)  scopus
18. L. Coregliano, A. Razborov, On the density of transitive tournaments, 2015 , 13 pp., arXiv: 1501.04074
19. 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  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi (cited: 1)  elib  scopus
20. S. I. Adian, “New Estimates of Odd Exponents of Infinite Burnside Groups”, Proc. Steklov Inst. Math., 289 (2015), 33–71  mathnet  crossref  crossref  isi (cited: 1)  elib (cited: 2 \citnumescopus 1)  elib (cited: 2 \citnumescopus 1)  scopus
21. S. I. Adian, Varuzhan Atabekyan, “Characteristic properties and uniform non-amenability of $n$-periodic products of groups”, Izv. Math., 79:6 (2015), 1097–1110  mathnet  crossref  crossref  mathscinet  adsnasa  isi (cited: 1)  elib
22. S. I. Adian, V. V. Benyash-Krivets, V. M. Buchstaber, E. I. Zel'manov, 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 (to the 75 anniversary since the birth of)”, Chebyshevskii Sb., 16:4 (2015), 6–10  mathnet
23. L. D. Beklemishev, A. A. Onoprienko, “On some slowly terminating term rewriting systems”, Sb. Math., 206:9 (2015), 1173–1190  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib  scopus
24. L. D. Beklemishev, A note on strictly positive logics and word rewriting systems, 2015 , 8 pp., arXiv: 1509.00666
25. 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, ISBN: 978-3-319-20296-9 , xx+443 pp.  crossref
26. L. D. Beklemishev, “Proof theoretic analysis by iterated reflection”, Turing’s Revolution, Part II, Springer, 2015, 225–270  crossref  scopus
27. T. Hartnick, A. Talambutsa, Relations between counting functions on free groups and free monoids, 2015 , 28 pp., arXiv: 1508.03166
28. M. Bucher, A. Talambutsa, Minimal exponential growth rates of metabelian Baumslag-Solitar groups and lamplighter groups, 2015 , 16 pp., Groups, Geometry, Dynamics (to appear), arXiv: 1506.03569
29. K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Inform. and Comput., 240 (2015), 56–73  mathnet  crossref  mathscinet  zmath  isi  elib  scopus
30. 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  mathnet (cited: 1)  crossref  mathscinet  zmath  isi (cited: 1)  scopus
31. 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  mathnet  crossref  mathscinet  scopus
32. 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  mathnet  crossref  mathscinet  zmath  scopus
33. 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 \citnumescopus 2, 2015, 317–328  mathnet  crossref  scopus
34. F. N. Pakhomov, “On Elementary Theories of Ordinal Notation Systems Based on Reflection Principles”, Proc. Steklov Inst. Math., 289 (2015), 194–212  mathnet  crossref  crossref  isi (cited: 1 \citnumescopus 1)  elib  elib  scopus
35. Fedor Pakhomov, Ordinal notations in Caucal hierarchy, 2015 , 15 pp., arXiv: 1512.05036
36. Daniyar Shamkanov, “Nested sequents for provability logic GLP”, Log. J. IGPL, 23:5 (2015), 789–815  mathnet  crossref  mathscinet  isi  elib  scopus
37. S. L. Kuznetsov, “On Translating Context-Free Grammars into Lambek Grammars”, Proc. Steklov Inst. Math., 290 (2015), 63–69  mathnet  crossref  crossref  isi  elib  elib  scopus
38. S. L. Kuznetsov, N. S. Ryzhkova, “Fragment ischisleniya Lambeka s iteratsiei”, Maltsevskie chteniya 2015 (Novosibirsk, 3–7 maya 2015 g.), Institut matematiki im. S.L. Soboleva SO RAN; Novosibirskii gos. universitet, Novosibirsk, 2015, 213 http://www.math.nsc.ru/conference/malmeet/15/malmeet15.pdf

   2014
39. A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254  mathnet  crossref  crossref  isi (cited: 1)  elib (cited: 1 \citnumescopus 1)  elib (cited: 1 \citnumescopus 1)  scopus
40. A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429  crossref  mathscinet (cited: 1)  zmath  isi (cited: 1)  elib (cited: 1 \citnumescopus 1)  scopus
41. Y. Li, A. Razborov, B. Rossman, “On the $AC^0$ complexity of subgraph isomorphism”, Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (Philadelphia, October 2014), IEEE, 2014
42. S. I. Adian, V. S. Atabekyan, “The Hopfian Property of $n$-Periodic Products of Groups”, Math. Notes, 95:4 (2014), 443–449  mathnet  crossref  crossref  isi (cited: 2 \citnumescopus 1)  elib  elib  scopus
43. L. D. Beklemishev, D. Fernández-Duque, J. J. Joosten, “On provability logics with linearly ordered modalities”, Studia Logica, 102:3 (2014), 541–566 , arXiv: 1210.4809  crossref  mathscinet (cited: 2)  isi (cited: 2)  elib (cited: 1)  scopus
44. L. Beklemishev, “Positive provability logic for uniform reflection principles”, Ann. Pure Appl. Logic, 165:1 (2014), 82–105  crossref  mathscinet (cited: 1)  zmath  isi  elib  scopus
45. L. Beklemishev, Y. Gurevich, “Propositional primal logic with disjunction”, J. Logic Comput., 24:1 (2014), 257–282  crossref  mathscinet  zmath  isi (cited: 3)  elib (cited: 3 \citnumescopus 5)  scopus
46. L. Beklemishev, D. Gabelaia, “Topological interpretations of provability logic”, Leo Esakia on duality in modal and intuitionistic logics, Outstanding Contributions to Logic, 4, eds. G. Bezhanishvili, Springer, 2014, 257–290  crossref
47. Lev Beklemishev, Ruy De Queiroz, Andre Scedrov, “Editors' foreword”, Journal of Computer and System Sciences, 80:6, Special Issue: 18th Workshop on Logic, Language, Information and Computation (WoLLIC 2011) (2014), 1037  crossref  isi
48. A. Semenov, S. Soprunov, V. Uspensky, “The lattice of definability. Origins, recent developments, and further directions”, Computer science—theory and applications, Lecture Notes in Comput. Sci., 8476, Springer, Cham, 2014, 23–38  crossref  mathscinet  zmath  scopus
49. V. L. Arlazarov, E. A. Dinitz, Yu. S. Ilyashenko, A. V. Karzanov, S. M. Karpenko, A. A. Kirillov, N. N. Konstantinov, M. A. Kronrod, O. P. Kuznetsov, L. B. Okun', P. A. Pevzner, A. L. Semenov, I. A. Faradzhev, B. V. Cherkasskii, A. G. Khovanskii, “Georgy Maksimovich Adelson-Velsky (obituary)”, Russian Math. Surveys, 69:4 (2014), 743–751  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
50. N. N. Andreev, V. M. Buchstaber, A. I. Garber, V. V. Kozlov, S. P. Konovalov, A. A. Mal'tsev, Yu. V. Nesterenko, S. P. Novikov, A. N. Parshin, I. Kh. Sabitov, A. L. Semenov, A. G. Sergeev, O. K. Sheinman, M. I. Shtogrin, E. V. Shchepin, “Nikolai Petrovich Dolbilin (on his 70th birthday)”, Russian Math. Surveys, 69:1 (2014), 181–182  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
51. Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii, “Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries”, Description Logics 2014, CEUR Workshop Proceedings, 2014, 45–57 http://ceur-ws.org/Vol-1193/paper_43.pdf
52. Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev, “The price of query rewriting in ontology-based data access”, Artificial Intelligence, 213 (2014), 42–59  crossref  mathscinet  zmath  isi (cited: 4)  elib (cited: 4 \citnumescopus 12)  scopus
53. Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev, “On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase”, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), ACM Digital Library, 2014, 57:1–57:10 , arXiv: 1401.4420
54. Fedor Pakhomov, “On the complexity of the closed fragment of Japaridze's provability logic”, Arch. Math. Logic, 53:7 (2014), 949–967  mathscinet  isi
55. F. Pakhomov, “Ordinal Notations and Fundamental Sequences in Caucal Hierarchy”, Logic Colloquium, Logic, Algebra and Truth Degrees. Abstract Booklet (Vienna, July 14–19), Kurt Gödel Society, 2014, 88
56. Fedor Pakhomov, “Complexity of Fragments of the Logic GLP”, Proof Theory, Modal Logic and Re ection Principles (Mexico City, September 29 – October 2, 2014), ITAM, 2014, 4
57. D. S. Shamkanov, “Circular Proofs for the Gödel–Löb Provability Logic”, Math. Notes, 96:4 (2014), 575–585  mathnet  crossref  crossref  zmath  isi  elib  elib  scopus
58. Daniyar Shamkanov, “Circular proofs for provability logic”, LOGIC COLLOQUIUM '13 (Evora, Portugal, July 22–27, 2013), The Bulletin of Symbolic Logic, 20, no. 2, 2014, 242–243 http://www.jstor.org/stable/23800717
59. D. Shamkanov, “Nested sequents for provability logic GLP”, Proof Theory, Modal Logic and Reflection Principles (Mexico City, Mexico, September 29 – October 2, 2014), Instituto Tecnologico Autonomo de Mexico, Mexico City, 2014, 20
60. S. Kuznetsov, “$L$-completeness of the Lambek calculus with the reversal operation allowing empty antecedents”, Categories and types in logic, language, and physics. Essays dedicated to Jim Lambek on the occasion of his 90th birthday, Lecture Notes in Comput. Sci., 8222, eds. C. Casadio, B. Coecke, M. Moortgat, P. Scott, Springer, Berlin, Heidelberg, 2014, 268–278  crossref  mathscinet  zmath  scopus
61. S. L. Kuznetsov, “Trivalent logics arising from L-models for the Lambek calculus with constants”, J. Appl. Non-Class. Log., 14:1-2 (2014), 132–137  crossref  mathscinet  scopus
62. S. Kuznetsov, “On translating context-free grammars into Lambek categorial grammars”, Joint Proceedings of the Second Workshop on Natural Language and Computer Science (NLCS’14) & 1st International Workshop on Natural Language Services for Reasoners (NLSR 2014), Affliated to RTA-TLCA, VSL 2014 (Vienna, July 17–18, 2014), eds. V. de Paiva, W. Neuper, P. Quaresma, C. Retoré, L. S. Moss, J. Saludes, Center for Informatics and Systems of the University of Coimbra, Coimbra, Portugal, 2014, 137–142 https://www.cisuc.uc.pt/ckfinder/userfiles/files/TR 2014-02.pdf

   2013
63. H. Hatami, J. Hladky, D. Král', S. Norin, A. Razborov, “On the number of pentagons in triangle-free graphs”, J. Combin. Theory Ser. A, 120:3 (2013), 722–732  crossref  mathscinet (cited: 13)  zmath  isi (cited: 10)  elib (cited: 7 \citnumescopus 13)  scopus
64. A. Razborov, “On the Caccetta-Häggkvist conjecture with forbidden subgraphs”, J. Graph Theory, 74:2 (2013), 236–248 , arXiv: 1107.2247  crossref  mathscinet (cited: 2)  zmath  isi (cited: 3)  elib (cited: 3 \citnumescopus 3)  scopus
65. E. Viola, A. Razborov, “Real advantage”, ACM Trans. Comput. Theory, 5:4 (2013), 17 , 8 pp.  crossref  mathscinet  scopus
66. A. A. Razborov, “What is a Flag Algebra?”, Notices Amer. Math. Soc., 60:10 (2013), 1324–1327  crossref  mathscinet
67. A. Razborov, “Flag algebras: an interim report”, Mathematics of Paul Erdős II, Springer, 2013, 207–232  crossref
68. A. A. Agrachëv, D. V. Anosov, S. M. Aseev, V. M. Buchstaber, A. M. Vershik, Ya. B. Vorobets, V. A. Kaimanovich, B. S. Kashin, I. G. Lysënok, A. Yu. Ol'shanskii, V. N. Remeslennikov, Ya. G. Sinai, S. K. Smirnov, A. M. Stepin, I. A. Taimanov, E. V. Shchepin, “Rostislav Ivanovich Grigorchuk (on his sixtieth birthday)”, Russian Math. Surveys, 68:5 (2013), 967–971  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
69. L. Beklemishev, D. Gabelaia, “Topological completeness of the provability logic GLP”, Ann. Pure Appl. Logic, 164:12 (2013), 1201–1223  crossref  mathscinet (cited: 5)  isi (cited: 5)  elib (cited: 4 \citnumescopus 3)  scopus
70. L. D. Beklemishev, “Pozitivnye logiki dokazuemosti”, Mezhdunarodnaya konferentsiya “Maltsevskie chteniya”. Tezisy dokladov (Novosibirsk, 11–15 noyabrya 2013 g.), FGBUN Institut matematiki im. S.L. Soboleva SO RAN; Novosibirskii gosudarstvennyi universitet, Novosibirsk, 2013, 10 www.math.nsc.ru/conference/malmeet/13/maltsev13.pdf
71. 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  mathnet
72. V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, Log. Methods Comput. Sci., 9:2 (2013), 13 , 17 pp.  crossref  mathscinet  zmath  isi  elib  scopus
73. K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Mathematical Foundations of Computer Science 2013, 38th International Symposium, MFCS 2013 (Klosterneuburg, Austria, August 26–30, 2013), Proceedings, Lecture Notes in Computer Science, 8087, Springer, Berlin–Heidelberg, 2013, 516–527 http://eccc.hpi-web.de/report/2013/021/  crossref  mathscinet (cited: 1 \citnumescopus 1)  zmath  scopus
74. S. Kikot, R. Kontchakov, V. V. Podolskii, M. Zakharyaschev, “Query Rewriting over Shallow Ontologies”, Description Logics 2013, Informal Proceedings of the 26th International Workshop on Description Logics (Ulm, Germany, July 23–26, 2013), CEUR Workshop Proceedings, 1014, CEUR Workshop Proceedings, 2013, 316–327 http://ceur-ws.org/Vol-1014/paper_27.pdf \citnumescopus 1  scopus
75. K. A. Hansen, R. I. Jensen, V. V. Podolskii, E. P. Tsigaridas, “Patience of matrix games”, Discrete Appl. Math., 161:16–17 (2013), 2440–2459  crossref  mathscinet  zmath  isi  elib  scopus
76. S. Kuznetsov, “Conjunctive grammars in Greibach normal form and the Lambek calculus with additive connectives”, Formal grammar. 17th and 18th international conferences, FG 2012, Opole, Poland, August 2012, revised selected papers, FG 2013, Düsseldorf, Germany, August 2013, Proceedings, Lecture Notes in Comput. Sci., 8036, Springer, Berlin, 2013, 242–249, ISBN: 978-3-642-39997-8/pbk  crossref  mathscinet  zmath  elib  scopus

   2012
77. O. Pikhurko, A. Razborov, Asymptotic structure of graphs with the minimum number of triangles, 2012 , To appear in “Combinatorics, Probability and Computing”, arXiv: 1204.2846
78. O. Beyersdorff, N. Galesi, M. Lauria, A. A. Razborov, “Parameterized bounded-depth Frege is not optimal”, ACM Transactions on Computation Theory, 4:3 (2012), 7 , 16 \citnumescopus 6 pp.  crossref  scopus
79. H. Hatami, J. Hladký, D. Král, S. Norin, A. Razborov, “Non-three-colourable common graphs exist”, Combin. Probab. Comput., 21:5 (2012), 734–742  crossref  mathscinet (cited: 8)  zmath  isi (cited: 5)  elib (cited: 4 \citnumescopus 8)  scopus
80. A. A. Razborov, Kommunikatsionnaya slozhnost, MTsNMO, 2012 s saita MTsNMO
81. S. I. Adian, “On a method for proving exact bounds on derivational complexity in Thue systems”, Math. Notes, 92:1 (2012), 3–15  mathnet  crossref  crossref  zmath  isi  elib  elib  scopus
82. L. D. Beklemishev, “Calibrating provability logic: from modal logic to reflection calculus”, Advances in Modal Logic, 9, eds. T. Bolander, T. Braüner, S. Ghilardi, L. Moss, College Publications, London, 2012, 89–94  zmath  elib
83. L. Beklemishev, D. Gabelaia, Topological interpretations of provability logic, 2012 , 37 pp., arXiv: 1210.7317
84. L. Beklemishev, G. Bezhanishvili, D. Mundici, Y. Venema, “Foreword [Special issue dedicated to the memory of Leo Esakia]”, Studia Logica, 100:1-2 (2012), 1–7  crossref  mathscinet  isi  scopus
85. L. Beklemishev, “DKAL: A Distributed Knowledge Authorization Language and Its Logic of Information”, Computer Science – Theory and Applications. 7th International Computer Science Symposium in Russia, CSR 2012 (Nizhny Novgorod, Russia, July 3–7, 2012), Lecture Notes in Computer Science, 7353, eds. E. Hirsch, J. Karhumäki, A. Lepistö, M. Prilutskii, Springer, 2012, XIII–XIV  crossref
86. M. Bucher, A. Talambutsa, Exponential growth rates of free and amalgamated products, Report No. 36, 2011/2012, spring, Institut Mittag-Leffler, Swedish Royal Academy of Science, Djursholm, 2012 , 17 pp. IML-1112s-36.pdf
87. V. V. Podolskii, “Exponential lower bound for bounded depth circuits with few threshold gates”, Inform. Process. Lett., 112:7 (2012), 267–271  crossref  mathscinet  zmath  isi  elib (cited: 1 \citnumescopus 1)  scopus
88. V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, How the World Computes, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 (Cambridge, UK, June 18–23, 2012), Proceedings, Lecture Notes in Comput. Sci., 7318, Springer–Berlin–Heidelberg, 2012, 599–608 , arXiv: 1204.2652  crossref  mathscinet  zmath  scopus
89. K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. P. Tsigaridas, Patience of matrix games, 2012 , 32 pp., arXiv: 1206.1751
90. S. Kikot, R. Kontchakov, V. V. Podolskii, M. Zakharyaschev, “Exponential lower bounds and separation for query rewriting”, Automata, Languages, and Programming, 39th International Colloquium, ICALP 2012 (Warwick, UK, July 9–13, 2012), Proceedings, Part II, Lecture Notes in Comput. Sci., 7392, Springer Berlin Heidelberg, 2012, 263–274 , arXiv: 1202.4193  crossref  mathscinet  zmath  elib (cited: 7 \citnumescopus 10)  scopus
91. F. N. Pakhomov, “Undecidability of the elementary theory of the semilattice of GLP-words”, Sb. Math., 203:8 (2012), 1211–1229  mathnet  crossref  crossref  mathscinet  zmath  isi (cited: 3)  elib (cited: 1 \citnumescopus 2)  elib (cited: 1 \citnumescopus 2)  scopus
92. S. Kuznetsov, “L-completeness of the Lambek calculus with the reversal operation”, Logical aspects of computational linguistics, Lecture Notes in Comput. Sci., 7351, Springer, Heidelberg, 2012, 151–160  crossref  mathscinet (cited: 2)  scopus
93. S. Kuznetsov, “Lambek grammars with the unit”, Formal grammar. 15th and 16th international conferences, FG 2010, Copenhagen, Denmark, August 2010, FG 2011, Ljubljana, Slovenia, August 2011. Revised selected papers, Lecture Notes in Comput. Sci., 7395, Springer, Berlin, 2012, 262–266, ISBN: 978-3-642-32023-1/pbk \citnumescopus 1  crossref  zmath  scopus
94. S. Kuznetsov, “Lambek grammars with one division and one primitive type”, Log. J. IGPL, 20:1 (2012), 207–221  crossref  mathscinet  zmath  isi (cited: 1 \citnumescopus 4)  scopus
95. S. L. Kuznetsov, Kategorialnye grammatiki, osnovannye na variantakh ischisleniya Lambeka, Diss. … kand. fiz.-matem. nauk, MGU imeni M. V. Lomonosova, M., 2012 , 70 pp. polnyi tekst (PDF), avtoreferat (PDF), English translation (PDF), English summary (PDF)

   2011
96. O. Beyersdorff, N. Galesi, M. Lauria, A. Razborov, “Parameterized bounded-depth Frege is not optimal”, Automata, languages and programming, Part I, Lecture Notes in Comput. Sci., 6755, Springer, Heidelberg, 2011, 630–641  crossref  mathscinet (cited: 1 \citnumescopus 2)  zmath  scopus
97. L. D. Beklemishev, V. M. Buchstaber, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, A. A. Razborov, A. L. Semenov, “Sergei Ivanovich Adian (on his eightieth birthday)”, Russian Math. Surveys, 66:1 (2011), 197–198  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
98. Alexander A. Razborov, “On the Fon-Der-Flaass interpretation of extremal examples for Turán's $(3,4)$-problem”, Proc. Steklov Inst. Math., 274 (2011), 247–266  mathnet  crossref  mathscinet  isi (cited: 6 \citnumescopus 7)  elib  scopus
99. J. Nordström, A. Razborov, “On minimal unsatisfiability and time-space trade-offs for $k$-DNF resolution”, Automata, languages and programming. Part I, 38th International Colloquium, ICALP 2011 (Zurich, Switzerland, July 4–8, 2011), Lecture Notes in Computer Science, 6755, eds. Luca Aceto, Monika Henzinger, Jiri Sgall, Springer, Heidelberg, 2011, 642–653  crossref  mathscinet (cited: 2)  zmath  scopus
100. M. Alekhnovich, A. Razborov, “Satisfiability, branch-width and Tseitin tautologies”, Comput. Complexity, 20:4 (2011), 649–678  crossref  mathscinet (cited: 3)  zmath  isi (cited: 1)  elib (cited: 2 \citnumescopus 3)  scopus
101. A. Borodin, T. Pitassi, A. Razborov, “Special Issue In Memory of Misha Alekhnovich. Foreword”, Computational Complexity, 20:4 (2011), 579–590  crossref  mathscinet  zmath  isi  elib  scopus
102. Igor G. Lysenok, Alexei G. Myasnikov, “A polynomial bound on solutions of quadratic equations in free groups”, Proc. Steklov Inst. Math., 274 (2011), 136–173  mathnet  crossref  mathscinet  isi (cited: 2 \citnumescopus 2)  elib  scopus
103. S. Adian, L. Beklemishev, A. Visser, “Proof and Computation”, J. Logic Computation, 21:4 (2011), 541–542  crossref  isi  scopus
104. P. S. Novikov, S. I. Adian, “On a semicontinuous function”, Proc. Steklov Inst. Math., 274 (2011), 4–8  mathnet  crossref  mathscinet  isi  elib  scopus
105. L. Beklemishev, D. Gabelaia, Topological completeness of the provability logic GLP, 2011 , 26 pp., arXiv: 1106.5693
106. L. Beklemishev, Y. Gurevich, Propositional primal logic with disjunction, Microsoft Research Technical Report MSR-TR-2011-35, Redmond, 2011 , 31 pp. http://research.microsoft.com/apps/pubs/default.aspx?id=146631
107. L. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic GLP”, Proc. Steklov Inst. Math., 274:1 (2011), 25–33  mathnet  crossref  mathscinet  isi (cited: 4)  elib (cited: 3 \citnumescopus 2)  elib (cited: 3 \citnumescopus 2)  scopus
108. L. Beklemishev, R. de Queiroz (eds.), Logic, language, information, and computation, 18th International Workshop, WoLLIC 2011 (Philadelphia, PA, USA, May 18–20, 2011), Proceedings, Lecture Notes in Comput. Sci., 6642, Springer, 2011 , x+311 pp.  crossref  zmath
109. L. Beklemishev, “Ordinal completeness of bimodal provability logic GLB”, Logic, language, and computation, 8th International Tbilisi Symposium TbiLLC 2009, Lecture Notes in Comput. Sci., 6618, eds. N. Bezhanishvili et al., Springer, Heidelberg, 2011, 1–15  crossref  mathscinet (cited: 2)  zmath  isi (cited: 3 \citnumescopus 1)  scopus
110. Algoritmicheskie voprosy algebry i logiki, Sbornik statei. K 80-letiyu so dnya rozhdeniya akademika Sergeya Ivanovicha Adyana, Tr. MIAN, 274, ed. L. D. Beklemishev, E. F. Mischenko, MAIK, M., 2011 , 351 pp.  mathnet
111. L. D. Beklemishev, “Foreword”, Proc. Steklov Inst. Math., 274 (2011), 1–3 \citnumescopus 4  mathnet  crossref  mathscinet  scopus  scopus
112. A. L. Semenov, S. F. Soprunov, “Finite quantifier hierarchies in relational algebras”, Proc. Steklov Inst. Math., 274 (2011), 267–272  mathnet  crossref  mathscinet  isi  elib (cited: 1 \citnumescopus 1)  elib (cited: 1 \citnumescopus 1)  scopus
113. A. L. Talambutsa, “On the attainability of the minimal growth exponent of free products of cyclic groups”, Russian Math. Surveys, 66:1 (2011), 179–180  mathnet  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib  scopus
114. A. L. Talambutsa, “Attainability of the minimal exponential growth rate for free products of finite cyclic groups”, Proc. Steklov Inst. Math., 274 (2011), 289–302  mathnet  crossref  mathscinet  isi (cited: 1 \citnumescopus 1)  elib  elib  scopus
115. Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246  mathnet  crossref  mathscinet  isi (cited: 1 \citnumescopus 1)  elib  scopus
116. Daniyar S. Shamkanov, “Interpolation properties for provability logics GL and GLP”, Proc. Steklov Inst. Math., 274 (2011), 303–316  mathnet  crossref  mathscinet  isi (cited: 2)  elib  scopus
117. D. S. Shamkanov, “Strong normalization and confluence for reflexive combinatory logic”, Logic, language, information and computation, 18th international workshop, WoLLIC 2011 (Philadelphia, PA, USA, May 18–20, 2011), Proceedings, Lecture Notes in Computer Science, 6642, eds. L. D. Beklemishev et al., Springer, Berlin, 2011, 228–238  crossref  zmath  isi  scopus
118. S. L. Kuznetsov, “On the Lambek calculus with a unit and one division”, Moscow University Math. Bull., 66:4 (2011), 173–175  crossref  mathscinet  elib  elib  scopus
Home page

© Steklov Mathematical Institute of RAS, 2004–2016