# Anatol Slissenko

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 superviser 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 was being written (see also.
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. This model allows the use of various operations, including multiplication, that without this bound on the length can give unrealistically fast algorithms. Besides that LRAM has a very dense time complexity hierarchy.
During 1981–1992 Slissenko was the head of a laboratory in St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences. 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 where he was the head of the Department of Computer Science whose creation he initiated (the student teams of the Department were world champions of ACM International Collegiate Programming Contest four times). In 1993–2009 he was a full professor at the University Paris-East Creteil at the Faculty of Science and Technology, Department of Informatics. Since 2009 he has remained a professor emeritus at this university.
He had also been the head (and, in a way, the founder) of Laboratory for Algorithmics Complexity and Logic (LACL) from 1997 until 2007. In all these positions he contributed to modernizing the curriculum and research.
In 1967 Slissenko organized together with Grigori Tseitin (1936–2022) and Robert I.Freidson (1942–2018) the Leningrad Seminar on Computational Complexity that first had its meetings in the Leningrad State University, and then in the Leningrad Department of Steklov Mathematical Institute (at that time Slissenko became its formal head). The seminar. played an important role in the development of this field in the Soviet Union. The seminar functioned until 1992, date on which after the collapse of the Soviet Union (and of its research system) the main part of its participants left the country and found jobs in USA, France, UK.
Historical information on the Soviet computer science can be found in, and some remarks are in.