Anatol Slissenko

Anatol Slissenko (Russian: Анатолий Олесьевич Слисенко) (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 and probabilistic models related to computer science.

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).

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(UPEC), France, and since 2009 he remains professor emeritus of this university. At UPEC he was the head (and in a way a founder) of Laboratory for Algorithmics Complexity and Logic (LACL) that he headed 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). Many mathematicians (among them Yuri Matiyasevich, Dima Grigoriev, E.Hirsch) started their research in his seminars for students.

A. 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 palidromes in real-time, 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), Slissenko graph-grammars (that describe classes of NP-hard problems solvable in polytime), decidable classes of verification of hard-real-time controllers, algorithms for constructing shortest paths among semi-algebraic obstacles, and entropy-like concepts for analysis of algorithms and inference systems.

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