Anatol Slissenko

From Wikipedia, the free encyclopedia
Anatol Slissenko (Slisenko) (Russian: Анатолий Олесьевич Слисенко)
Born (1941-08-15) 15 August 1941 (age 81)
NationalityRussian, French
Alma materSaint Petersburg State University
Scientific career
FieldsComputer Science
InstitutionsSteklov Mathematical Institute
Saint Petersburg State University
Leningrad Institute for Informatics and Automation of the USSR Academy of Sciences
Paris-Est Créteil Val-de-Marne University
Leningrad Polytechnical Institute
Doctoral advisorNikolai Aleksandrovich Shanin
Doctoral studentsDmitry Grigoriev

Anatol Slissenko (Russian: Анатолий Олесьевич Слисенко[1]) (born August 15, 1941) is a Soviet, Russian and French mathematician and computer scientist. Among his research interests one finds automatic theorem proving, recursive analysis, computational complexity, algorithmics, graph grammars, verification, computer algebra, entropy[2] and probabilistic models related to computer science.[3][4]

Early years[edit]

Anatol Slissenko was born in Siberia, where his father served as head of a regiment of military topography. He graduated from the Leningrad State University, Faculty of Mathematics and Mechanics in 1963 (honors diploma).

Academic career[edit]

He earned his PhD (candidate of sciences, his adviser was Nikolai Aleksandrovich Shanin) in 1967 from the Leningrad Department of Steklov Institute of Mathematics, and his Doctor of Science (higher doctorate) in 1981 from the Steklov Institute of Mathematics in Moscow.

During 1963–1981 he was with the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences (LOMI). From 1967 till 1992 he headed the Leningrad Seminar on Computational Complexity that played an important role in the development of this field in the Soviet Union.

During 1981–1993 he was the head of Laboratory of Theory of Algorithms at the Leningrad Institute for Informatics and Automation of the USSR Academy of Sciences. From 1993 until 2009 he was a full professor of the University Paris-Est Créteil, France, and since 2009 he remains professor emeritus of this university. He had also been head (and in a way a founder) of Laboratory for Algorithmics Complexity and Logic from 1997 until 2007.

In 1981–1987 he was a part-time professor of the Leningrad Polytechnical Institute, and during 1988–1992 he was a professor and head of the Department of Computer Science at Leningrad State University, Faculty of Mathematics and Mechanics, whose creation he initiated (the teams of the Department were world champions of ACM International Collegiate Programming Contest four times).[5] Many mathematicians (among them Yuri Matiyasevich, Dima Grigoriev, E.Hirsch) started their research in his seminars for students.

Slissenko was invited as a speaker at many conferences, in particular at International Congress of Mathematicians in 1983, in Warsaw, Poland.


Among his results one can mention a six-head one-tape Turing machine that recognizes palindromes in real-time,[6] an algorithm (for a kind of pointer machine) that solves in real-time a large variety of string-matching problems (including finding of all periodicities in a compact form),[7] Slissenko graph-grammars (that describe classes of NP-hard problems solvable in polytime),[8] decidable classes of verification of hard-real-time controllers,[9] algorithms for constructing shortest paths among semi-algebraic obstacles,[10][11] and entropy-like concepts for analysis of algorithms and inference systems.[12][13]

He collaborated with N.Shanin, S.Maslov, G.Mints and V.Orevkov on automatic theorem proving, and with D.Beauquier[9] D.Grigoriev, D.Burago, A.Rabinovich, P. Vasilyev[14] and others on some algorithmic problems, see.[15]


  1. ^ "Слисенко Анатолий Олесьевич"
  2. ^ Anatol Slissenko. On entropic measures of computations
  3. ^ Publications in Math-Net.Ru(Russian)
  4. ^ French publications list
  5. ^ Anatol Slissenko's ACM Senior Member award
  6. ^ A. Slisenko. Recognizing a symmetry predicate by multihead Turing machines with input. Proc. Steklov Inst. of Mathematics, AMS, 129:25–208, 1976. In Russian: Trudy Matematicheskogo Instituta Akademii Nauk SSSR, 129:30–202, 1973.
  7. ^ A. Slisenko. Detection of periodicities and string-matching in real time. J. of Soviet Mathematics, 22(3):1316-1386, 1983. In Russian: Zapiski Nauchnykh Seminarov LOMI, 105:62–173, 1981.
  8. ^ A. Slissenko. Context-free grammars as a tool for describing polynomial-time subclasses of hard problems. Inf. Process. Lett., 14(2):52–56, 1982.
  9. ^ a b Danièle Beauquier, Anatol Slissenko. A first order logic for specification of timed algorithms: basic properties and a decidable class. Annals of Pure and Applied Logic, 113(1–3):13–52, 2002.
  10. ^ J. Heintz, T. Krick, A. Slissenko, P. Solerno. Finding shortest paths around semi-algebraic obstacles in the plane, J. of Math. Sci., 70(4):1944–1949, 1994. In Russian: Zapiski Nauchnykh Seminarov LOMI, 192:164–174, 1991.
  11. ^ D. Grigoriev, A. Slissenko. Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane, St. Petersburg Math. J., 10(2):315–332, 1999. In Russian: Algebra and Analysis, 10(2):124–147, 1998.
  12. ^ A. Slissenko. On measures of information quality of knowledge processing systems. Information Sciences: An International Journal, 57–58:389–402, 1991.
  13. ^ A. Slissenko. On entropic convergence of algorithms in terms of domain partitions. 19 pages, 2016. [1]
  14. ^ Anatol Slissenko, Pavel Vasilyev. Simulation of Timed Abstract State Machines with Predicate Logic Model-Checking. Journal of Universal Computer Science.
  15. ^ Anatol Slissenko's homepage

External links[edit]