Anatoly Olesievich Slisenko

Anatol Slissenko (a former transliteration: Slisenko; Russian: Анатоль Олесьевич Слисенко), a Soviet, Russian and French mathematician and computer scientist, was born on August 15, 1941, in Siberia, where his father served as the commander of a regiment of military topography. In 1950 his parents moved to Leningrad.

Research Source:

In 1958 A.O. Slissenko entered the Faculty of Mathematics and Mechanics of Leningrad (now Saint Petersburg) State University. There he started his research in constructive mathematics (recursive analysis) under the supervision of Nikolai Shanin. Having graduated from the university in 1963, he became a researcher at the Leningrad Department of Steklov Mathematical Institute of the Academy of Sciences of the USSR (nowadays it is called slightly differently). He defended his PhD dissertation in constructive mathematics 1967, his supervisor was Nikolai Shanin. In 1981 he defended his DSc dissertation at Steklov Mathematical Institute in Moscow.

In 1963–1966 he continued his research in constructive mathematics and at the same time he participated in the development and implementation of Shanin's algorithm for automatic theorem proving in classical propositional logic.

Then he gradually began a research in algorithmics and computational complexity.

In paper he discusses how to define 'computational' complexity of an individual problem, a topic that influenced his subsequent papers on entropic convergence.

In he gave an unexpected solution to the problem of recognizing palindromes by multi-head Turing machines, namely, he proved that a 6-headed Turing machine with one tape can recognize palindromes in real time; the widespread expectation was that it was impossible. His very long proof was later simplified by Zvi Galil who used some new results that were not known when

Another major result of Slissenko was a real-time algorithm that solved a large variety of string-matching problems (including finding of all periodicities in a compact form). The algorithm can be formalized as LRAM (address machine), a random access machine with registers whose length is bounded by the logarithm of time complexity, introduced in and also described in. He worked there on applications, however it was a time of agony of the Soviet Union, and there were no noteworthy publications in this field.

In he introduced a class of graph grammars (called Slisenko (Slissenko) grammars in ) that generate graphs for which the existence of Hamiltonian cycles can be decided in polynomial time. The graphs generated by these grammars are of bounded tree-width.

The paper was his first one where he introduced an entropy to evaluate the quality of inference systems.

From 1993 until 2009 he was a professor at the University Paris-East Créteil (UPEC: Université Paris-Est-Créteil; the previous name was Paris-12 University), Faculty of Sciences and Technology, Department of Informatics. He worked on the complexity of Markov decision processes, on algorithms constructing shortest paths amidst semi-algebraic and other obstacles and on the verification of timed systems.

Paper describes a polytime algorithm for constructing a shortest path touching skew straight lines in 3-dimensional space that solves a known open problem.

A model checking algorithm for a rather powerful logic with an operator of probability was developed in; it was a first result for this kind of logics.

Various topics of verification were investigated for timed models. In a powerful logic for the specification of hard real time systems, named FOTL (First Order Timed Logic), was introduced and decidable classes were presented. More general decidable classes were investigated in.

Entropic convergence of algorithms was introduced in; it was applied to knowledge bases evaluation.

In he noticed that one can slightly reformulate P≠NP problem in such a way that it remains practically interesting but its independence from arithmetics implies that P≠NP.

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

He collaborated with Nikolai Shanin, S.Maslov, G.Mints and V.Orevkov on automatic theorem proving, with D.Beauquier, Dima Grigoriev, D.Burago, A.Rabinovich and others on various topics related to algorithmics.

Teaching and Organizational Activity A.O.Slissenko was a part-time professor in Leningrad Polytechnical Institute in 1981–1987, and in 1988–1992 he was a part-time professor in the faculty of Mathematics and Mechanics of Leningrad State University and some remarks are in.