Theoretical Computer Science


Publications

2017

  1. N.N. Kuzyurin On the problem of finding approximation of bipatite cliques Proceedings of the Institute for System Programming. Volume 29, issue 3, 2017 . pp. 225-232.

2015

  1. V.A.Zakharov, V.V.Podymov On the application of equivalence checking algorithms for program minimization Proceedings of the Institute for System Programming. Volume 27, issue 4, 2015 . pp. 145-174.
  2. A.S. Asratian, N.N. Kuzyurin Approximating Chromatic Sum Coloring of Bipartite Graphs in Expected Polynomial Time Proceedings of the Institute for System Programming. Volume 27, issue 5, 2015 . pp. 191-198.
  3. D.A. Grushin, N.N. Kuzyurin Load Balancing in Unihub SaaS System Based on User Behavior Prediction Proceedings of the Institute for System Programming. Volume 27, issue 5, 2015 . pp. 23-34.

2014

  1. Chemeritsky E.V., Smeliansky R.L., Zakharov V.A. A formal model and verification problems for Software Defined Networks. Automatic Control and Computer Sciences, Allerton Press Inc. (United States), 2014, vol. 48, № 7, pp. 398-406.
  2. Altukhov V.S., Chemeritskiy E.V., Podymov V.V., Zakharov V.A. A runtime verification system for Software Defined Networks. Proceedings of the International Conference "Tools & Methods of Program Analysis", TMPA-2014, 2014, Kostroma, KSTU, pp. 19-28.
  3. Chemeritskiy E.V., Zakharov V.A. Constitent network update without tagging. SDN&NFV:The Next Generation of Computational. Infrastructure: 2014 International Scientific and Technology Conference "Modern Networking Technologies (MoNeTec)", 2014, pp. 47-52.
  4. Konnov I.V., Podymov V.V., Volkanov D.Yu, Zorin D.A., Zakharov V.A. How to make a simple tool for verification of real-time systems. Automatic Control and Computer Sciences, Allerton Press Inc. (United States), 2014, vol 48, № 7, pp. 534-542.
  5. Novikova T.A., Zakharov V.A. On the complexity of the solution problem for linear equations over finite substitutions.
  6. Zakharov V.A. On the equivalence of bounded-nondeterministic transducers over semigroups.
  7. Chemeritskiy E.V., Zakharov V.A. On the Network Update Problem for Software Defined Networks. Proceedings of the 5th Workshop "Program Semantics, Specification and Verification: Theory and Applications", 2014, Издательский дом ГУ ВШЭ Москва, pp. 26-37.
  8. V.A. Zakharov, E.V. Chemeritsky On the update problems for Software Defined Networks.
  9. Novikova T.A., Zakharov V.A. Two-sided unification is NP-complete. Proceedings of the 28th International Workshop on Unification (UNIF-2014), RISC-Linz Report Series, 2014, JKU Linz, Vienna, Austria, vol. 6, p. 55-61.
  10. Altukhov V.S., Chemeritskiy E.V., Podymov V.V., Zakharov V.A. VERMONT - a toolset for checking SDN packet forwarding policies on-line. SDN&NFV:The Next Generation of Computational. Infrastructure: 2014 International Scientific and Technology Conference "Modern Networking Technologies (MoNeTec)", 2014, pp. 7-12.
  11. N.N. Kuzyurin, D.A. Grushin, S.A. Fomin. Two-dimensional packing problems and optimization in distributed computing systems. Proceedings of the Institute for System Programming. Volume 26, issue 1, 2014 . pp. 483-502.
  12. T.A. Novikova, V.A. Zakharov. Two-sided program unification and its application to program refactoring. Proceedings of the Institute for System Programming. Volume 26, issue 2, 2014 . pp. 245-268.
  13. Varnovskij N.P., Martishin S.А., Khrapchenko M.V., Shokurov А.V. A Threshold Cryptosystem in Secure Cloud Computations. Proceedings of the Institute for System Programming. Volume 26, issue 2, 2014 . pp. 269-274.
  14. V.V. Podymov, V.A. Zakharov. A polynomial algorithm for checking the equivalence in models of programs with commutation and vast operators. Proceedings of the Institute for System Programming. Volume 26, issue 3, 2014 . pp. 145-166.
  15. N.P. Varnovsky, V.A.Zakharov, N.N. Kuzurin, V.A. Shokurov. The current state of art in program obfuscations:definitions of obfuscation security. Proceedings of the Institute for System Programming. Volume 26, issue 3, 2014 . pp. 167-198.

2013

  1. Novikova T.A., Zakharov V.A. Is it possible to unify sequential programs. Proceedings of the 27-th International Workshop on Unification, June 26, 2013, Eindhoven, EPiC Series, 2013, vol. 123, pp. 36-46.
  2. Podlovchenko R.I., Zakharov V.A. On two techniques for equivalence checking in algebraic models of programs.
  3. Alexander Shokurov. On Solving The Systems of Algebraic Equations Using Gröbner Bases. Proceedings of the Institute for System Programming. Volume 25, 2013 . pp. 195-206.

2012

  1. Zakharov V.A. Models and algorithms in the equivalence-checking problem for sequential programs.
  2. Konnov I.V., Podymov V.V., Volkanov D.Yu, Zorin D.A., Zakharov V.A. On the Designing of Model Checkers for Real-Time Distributed Systems. Proceedings of the 3-rd Workshop "Program Semantics, Specification, and Verification: Theory and Applications", Nizhni Novgorod, Russia, July 1-2, 2012, 2012, Novgorod, Russia, pp. 72-81.
  3. Zakharov V.A., Novikova T.A. On the logic-and-term equivalence of first-order programs.
  4. M.M. Bernovskiy, N.N. Kuzyurin. Random graphs, models and generators of scale-free graphs. Proceedings of the Institute for System Programming. Volume 22, 2012 . pp. 419-434.
  5. V.A.Zakharov, T.A. Novikova. Polynomial time algorithm for checking strong equivalence of program. Proceedings of the Institute for System Programming. Volume 22, 2012 . pp.435-455.
  6. A.V. Shokurov. Comparing complexities of problems of determining of Grebner’s basis of ideal and solving this ideal. Proceedings of the Institute for System Programming. Volume 22, 2012 . pp. 463-474.
  7. A.V. Shokurov, K.V. Sergeev. On Constructing a Fully Homomorphic Encryption. Proceedings of the Institute for System Programming. Volume 23, 2012 . pp. 427-432.
  8. D.A. Grushin, N.N. Kuzyurin. Energy-efficient computations on a group of clusters. Proceedings of the Institute for System Programming. Volume 23, 2012 . pp. 433-446.
  9. V.A.Zakharov, T.A. Novikova. Polynomial time algorithm for checking strong equivalence of program. Proceedings of the Institute for System Programming. Volume 23, 2012 . pp. 455-476.

2011

  1. Zakharov V.A. Program equivalence checking by two-tape automata. Cybernetics and Systems Analysis, 2011, vol 46, № 4, pp. 554-562.
  2. V.A. Zakharov, T.A. Novikova. On the application of substitution algebra to program unification. Proceedings of the Institute for System Programming. Volume 21, 2011 . pp. 141-166.

2010

  1. Konnov I.V., Zakharov V.A. An invariant-basedё approach to the verification of asynchronous parameterized networks. Journal of Symbolic Computation, Academic Press (United States),vol. 45, № 11, pp. 1144-1162.
  2. V.A. Zakharov Equivalence checking of sequential programs with the help of two-tape automata.
  3. Zakharov V.A., Konnov I.V. Using adaptive symmetry reduction for LTL model checking.
  4. R. I. Podlovchenko, N. N. Kuzyurin, V. S. Shcherbina, V. A. Zakharov Using algebraic models of programs for detecting metamorphic malwares.
  5. D.A. Grushin, A.I. Pospelov. Grid modeling environment: implementation and application. Proceedings of the Institute for System Programming. Volume 18, 2010 . pp. 243-260.
  6. Sergey A. Martishin, Marina V. Khrapchenko. The algorithm on base of Nelder–Mead modified method and genetic algorithm for strip packing problem. Proceedings of the Institute for System Programming. Volume 19, 2010 . pp. 135-156.
  7. N.N.Kuzjurin, A.I. Pospelov. Probabilistic analysis a algorithm for strip packing. Proceedings of the Institute for System Programming. Volume 19, 2010 . pp. 157-164.

2009

  1. Bulychev P.E., Kostylev E.V., Zakharov V.A. Anti-unification algorithms and their applications in program analysis. Proceedings of the 7th International Conference "Perspectives of System Informatics", June 15-19, 2009, Novosibirsk, серия Lecture Notes in Computer Science, 2014, vol. 5947, pp. 413-424.
  2. Khoroshilov A., Petrenko A., Mutilin V., Zakharov V.A. Establishing Linux Driver Verification Processes. Proceedings of the 7th International Conference "Perspectives of System Informatics", June 15-19, 2009, Novosibirsk, серия Lecture Notes in Computer Science, 2009, Springer, vol. 5947, с. 165-176.
  3. Zakharov V.A. Two-tape machinery for the equivalence checking of sequential programs. Proceedings of the International Workshop on Program Understanding, June 20-22, 2009, Novosibirsk, 2009, Novosibirsk, pp. 28-40.

2008

  1. Khoroshilov A., Mutilin V., Shcherbina V., Strikov O., Vinogradov S., Zakharov V.A. How to cook an automated system for Linux driver verification. Proceedings of the 1st Spring Young Researchers’ Colloquium on Software Engineering SYRCoSE 2008 (St Petersburg, May 29-30, 2008), 2008, Санкт-Петербург, с. 15-19.

2007

  1. Konnov I.V., Zakharov V.A. An invariant-based approach to the verification of asynchronous parameterized networks. Proceedings of the 1-st International Workshop on Invariant Generation, June 25-26, 2007, Hagenberg, Austria, 2007, Hagenberg, Austria, pp. 41-55.
  2. Kuzurin N.N., Shokurov A.V., Varnovskij N.P., Zakharov V.A. On the concept of software obfuscation in computer security. Proceedings of the 7-th Information Security Conference (ISC'07), Valparaiso, Chile, серия Lecture Notes in Computer Science, 2007, vol. 4779, pp. 281-298.
  3. Н.Н. Кузюрин, А.И. Поспелов. Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу. Proceedings of the Institute for System Programming. Volume 12 (in Russian), 2007 . Стр. 17-26.

2006

  1. Ciobanu G., Zakharov V.A. Encoding mobile ambients into the pi-calculus. Proceedings of the Andrei Ershov 6th International Conference «Prespectives of System Informatics» (27-30 June 2006, Novosibirsk), Lecture Notes in Computer Science, 2006, Springer Berlin, vol. 4378, pp. 148-161.
  2. Podlovchenko R.I., Rusakov D.M., Zakharov V.A. On the equivalence problem for programs with mode switching. Proceedings of CIAA-2005 "The 10-th International Conference on Implementation and Application of Automata" (June 27-29, 2005), Sophia Antipolis, France, Lecture Notes in Computer Science, 2006, vol. 3845, pp. 351-352.

2005

  1. Zakharov V.A., Zakharyaschev I.M. An equivalence-checking algorithm for polysemantic models of sequential programs. Proceedings of the International Workshop on Program Understanding (14-16 July, 2003, Altai Mountains), 2005, Novosibirsk, pp. 59-70.
  2. Zakharov V.A., Zakharyaschev I.M. On the equivalence checking problem for a model of programs related with muti-tape automata. Proceedings of the 9-th International Conference on Implementation and Application of Automata (CIAA'04), July 22-24, 2004), Kingston, Ontario, Canada, Lecture Notes in Computer Science, 2005, vol. 3317, pp. 293-305.

2004

  1. А.Я. Калинов, А.С. Косачёв, М.А. Посыпкин, А.А. Соколов. Автоматическая генерация тестов для графического пользовательского интерфейса по UML диаграммам действий. Proceedings of the Institute for System Programming. Volume 8, issue 1 (in Russian), 2004 . Стр. 99-116.
  2. А.И. Аветисян, С.С. Гайсарян, Д.А. Грушин, Н.Н. Кузюрин, А.В. Шокуров. Эвристики распределения задач для брокера ресурсов Grid. Proceedings of the Institute for System Programming. Volume 5 (in Russian), 2004 . Стр. 269-280.
  3. Н.Н. Кузюрин, С.А. Фомин. Покрытие графов циклами и быстрое восстановление оптоволоконных сетей. Proceedings of the Institute for System Programming. Volume 5 (in Russian), 2004 . Стр. 249-268.
  4. N.N. Kuzjurin. Probabilistic analysis of the greedy algorithm. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 101-108.
  5. Н.Н. Кузюрин, С.А. Мартишин, М.В. Храпченко. Генетические алгоритмы в задаче поиска часто встречающихся комбинаций. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 109-126.
  6. N.P. Varnovsky. A note on the concept of obfuscation. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 127-136.
  7. С.Н. Жук. Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 13-26.
  8. K.S. Ivanov, V.A. Zakharov. Program obfuscation as obstruction of program static analysis. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 137-156.
  9. A.V. Shokurov. An approach to quantitative analysis of resistance of equivalent transformations of algebraic circuits. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 157-178.
  10. I.M. Zakharyaschev, V.A. Zakharov. On the equivalence-checking problem for polysemantic models of sequential programs. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 179-198.
  11. С.А. Фомин. Быстрый приближенный алгоритм для задачи положительного линейного программирования. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 27-40.
  12. Н.Н. Кузюрин, О.А. Прокопьев. О распознавании сложности аппроксимации булевых функций. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 41-50
  13. А.И. Поспелов. Анализ одного алгоритма упаковки прямоугольников, связанного с построением расписаний для кластеров. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 7-12.
  14. Н.Н. Кузюрин. Обобщенные покрытия и их аппроксимации. Proceedings of the Institute for System Programming. Volume 6 (in Russian), 2004 . Стр. 85-100.

2003

  1. Varnovskij N.P., Zakharov V.A. On the possibility of provably secure obfuscating programs. Proceedings of the Andrei Ershov 5th International Conference «Prespectives of System Informatics» (PSI'03) , 9-12 July 2003, Novosibirsk, 2003, Lecture Notes in Computer Science, место издания Springer, том 2890, pp. 91-102.

2001

  1. Chow S., Gu Y., Johnson H., Zakharov V.A. An approach to the obfuscation of control-flow of sequential computer programs. Proceedings of the First "Information Security Conference", Malaga, Spain, 2001, серия Lecture Notes in Computer Science, 2001, v. 2200, pp. 144-155.
  2. Zakharov V.A. The equivalence problem for computational models: decidable and undecidable cases. Proceedings of the Third International Conference, MCU 2001 Chişinau, Moldova, May 23–27, 2001, Lecture Notes in Computer Science, v. 2055, pp. 133-153.

2000

  1. Zakharov V.A. On the decidability of the equivalence problem for monadic recursive programs. RAIRO - Theoretical Informatics and Applications, издательство EDP Sciences (France), 2000, v 34, № 2, pp. 157-171.
  2. Н.Н. Кузюрин, В.А. Захаров, А.Н. Холодов, Л.В. Шабанов, А.В. Шокуров. Эффективные алгоритмы и их программные реализации. Proceedings of the Institute for System Programming. Volume 1 (in Russian), 2000 . Стр. 138-148.

1978-1997

  1. N.N. Kuzjurin, L.V. Shabanov A parallel algorithm for fixed-dimensional linear programming Parallel Algorithms and Applications, 1995, v. 5, N 34, 17-24.