Anatol Slissenko

Source:{{Cite journal |last1=Beauquier |first1=D. |last2=Grigoriev |first2=D. |last3=Matiyasevich |first3=Yu. |date=2003 |title=Biography of A.O. Slissenko |journal=Theoretical Computer Science |volume=303 |pages=3–5}}

In 1958 A.O. Slissenko entered the Faculty of Mathematics and Mechanics of Leningrad (now Saint Petersburg) State University.{{Cite web|url=https://math.spbu.ru/en/|title=Mathematics & Mechanics Faculty of St. Petersburg State University.|website=math.spbu.ru}}{{clarify|date=March 2025}} There he started his research A. Slisenko (Slissenko). On some algorithmic problems, concerning arithmetical operations on duplexes. Soviet Mathematical Doklady, 152(2), 1963. Russian original in: Doklady Akademii Nauk SSSR, 152(2):292–295, 1963. in constructive mathematics (recursive analysis){{Cite book|url=https://plato.stanford.edu/entries/mathematics-constructive/|title=The Stanford Encyclopedia of Philosophy|first1=Douglas|last1=Bridges|first2=Erik|last2=Palmgren|first3=Hajime|last3=Ishihara|editor-first1=Edward N.|editor-last1=Zalta|editor-first2=Uri|editor-last2=Nodelman|date=March 12, 2022|publisher=Metaphysics Research Lab, Stanford University|via=Stanford Encyclopedia of Philosophy}} 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.{{Cite web |title=History of the Institute {{!}} St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences |url=https://www.pdmi.ras.ru/pdmi/en/history |website=www.pdmi.ras.ru}} 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.N. Shanin, G. Davydov, S. Maslov, G. Mints, V. Orevkov, and A. Slissenko (Slissenko). An algorithm for machine search of a natural logical deduction in a propositional calculus. In J. Siekmann and G. Wrightson, editors, *The Automation of Reasoning I: Classical Papers on Computational Logic 1957–1966*, pages 424–483. Springer-Verlag, 1983 (Russian original was published by Nauka, Leningrad, 1965, 39p.).

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

In paper A. Slisenko. Finite approach to the problem of optimizing theorem-proving algorithms. J. of Soviet Mathematics, 10(4):597–603, 1978. Russian original in: Zapiski Nauchnykh Seminarov LOMI, 49:123-130, 1975. he discusses how to define 'computational' complexity of an individual problem, a topic that influenced his subsequent papers on entropic convergence.

In A. Slisenko . Recognizing a symmetry predicate by multihead turing machines with input. Proc. Steklov Inst. of Mathematics, 129:25–208, 1976. Russian original in:Trudy Matematicheskogo Instituta Akademii Nauk SSSR, 129:30–202, 1973. 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.A. Slisenko. A simplified proof of real-time recognizability of palindromes on Turing machines. J. of Soviet Mathematics, 15(1):68–77, 1981. Russian original in: Zapiski Nauchnykh Seminarov LOMI, 68:123–139, 1977.

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).A. Slissenko. Detection of periodicities and string-matching in real time. J. of Soviet Mathmatics, 22(3):1316–1386, 1983. Russian original in: Zapiski Nauchnykh SeminarovnLOMI, 105:62–173, 1981. 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 A. Slissenko. Models of computations based on address organization of storage. In Proc. Soviet Symp. on AI and Automation of Research in Mathematics, Kiev, pages 94–96. Institute of Cybernetics, Kiev, 1978 (In Russian). and also described in.A. Slissenko. Complexity problems of theory of computation. Russian Mathematical Surveys, 36(6):23–125, 1981. Russian original in: Uspekhi Matem. Nauk, 36(2):21–103, 1981. 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.{{Cite web|url=http://www.spiiras.nw.ru/en/|title=Main - SPIIRAS|website=www.spiiras.nw.ru}} 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 {{Cite journal |last=Slisenko |first=A. |date=1982 |title=Context-free grammars as a tool for describing polynomial-time subclasses of hard problems |journal=Information Processing Letters |volume=14 |issue=2 |pages=52–56|doi=10.1016/0020-0190(82)90086-2 }} he introduced a class of graph grammars (called Slisenko (Slissenko) grammars in A. Habel, Hyperedge replacement: grammars and languages, in: Lecture Notes in Computer Science, Vol. 643, Springer, Berlin, 1992) 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 {{Cite journal |last=Slissenko |first=A. |date=1991 |title=On measures of information quality of knowledge processing systems |journal=Information Sciences |volume=57-58 |pages=389–402|doi=10.1016/0020-0255(91)90089-D }} 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{{Cite web|url=https://www.en.u-pec.fr/|title=UPEC|website=UPEC}} (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,{{Cite journal |last1=Burago |first1=D. |last2=de Rougemont |first2=M. |last3=Slissenko |first3=A. |date=1996 |title=On the complexity of partially observed Markov decision processes |journal=Theoret. Comput. Sci. |volume=157 |issue=1 |pages=161–183|doi=10.1016/0304-3975(95)00158-1 |doi-access=free }} on algorithms constructing shortest paths amidst semi-algebraic and other obstacles and on the verification of timed systems.

Paper {{Cite journal |last1=Burago |first1=D. |last2=Grigoriev |first2=D. |last3=Slissenko |first3=A. |date=2004 |title=Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon |journal=Theoretical Computer Science |volume=315 |issue=2–3 |pages=371–404}} 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;{{Cite journal |last1=Beauquier |first1=D. |last2=Rabinovich |first2=A. |last3=Slissenko |first3=A. |date=2006 |title=A logic of probability with decidable model-checking |journal=Journal of Logic and Computation |volume=16 |issue=4 |pages=461–487}} it was a first result for this kind of logics.

Various topics of verification were investigated for timed models. In {{Cite journal |last1=Beauquier |first1=D. |last2=Slissenko |first2=A. |date=2002 |title=A first order logic for specification of timed algorithms: Basic properties and a decidable class |journal=Annals of Pure and Applied Logic |volume=113 |issue=1–3 |pages=13–52}} 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.{{Cite journal |last1=Beauquier |first1=D. |last2=Slissenko |first2=A. |date=2006 |title=Periodicity based decidable classes in a first order timed logic |journal=Annals of Pure and Applied Logic |volume=139 |issue=1–3 |pages=43–73}}

Entropic convergence of algorithms was introduced in;A. Slissenko. On entropic convergence of algorithms. In A. Blass, P. Cgielski, N. Dershowitz, M. Droste, and B. Finkbeiner, editors, Fields of Logic and Computation III. Lecture Notes in Computer Science, vol 12180, pages 291–304. Springer, Cham, 2020. it was applied to knowledge bases evaluation.A.Slissenko. Relating Information and Proof. 9 pages. To be published under the title "Relating Information and Knowledge". http://arxiv.org/abs/2205.07635

In A. Slissenko. St.Petersburg/Leningrad (1961-1998): From Logic to Complexity and Further, In: "People and Ideas In Theoretical Computer Science", Springer Verlag, pages 274-313, 1998. ISBN 981-4021-13-X 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.A. Slissenko. Linguistic considerations in devising effective algorithms. In Proc. Intern. Congress of Mathematicians, August 16–24, 1983, Waszawa, pages 347–357. ICM, Waszawa, 1984.

He collaborated with Nikolai Shanin, S.Maslov, G.Mints and V.Orevkov{{Cite web |title=Vladimir Orevkov {{!}} St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences |url=https://www.pdmi.ras.ru/pdmi/en/staff/vladimir-orevkov |website=www.pdmi.ras.ru}} on automatic theorem proving, with D.Beauquier, Dima Grigoriev, D.Burago, A.Rabinovich{{Cite web|url=https://english.tau.ac.il/profile/rabinoa|title=Prof. Alexander Rabinovich|website=Tel Aviv University}} and others on various topics related to algorithmics.{{Cite web|url=https://www.lacl.fr/slissenko/anatol_pub.html|title=anatol_pub.html|website=www.lacl.fr}}{{Cite web|url=https://www.mathnet.ru/rus/person19146|title=Персоналии: Слисенко Анатоль Олесьевич|website=www.mathnet.ru}}

A.O.Slissenko was a part-time professor in Leningrad Polytechnical Institute{{Cite web|url=https://en.wikipedia.org/wiki/Peter_the_Great_St._Petersburg_Polytechnic_University|title=Peter the Great St. Petersburg Polytechnic University|date=February 13, 2025|via=Wikipedia}} 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,A. Slissenko. A view on recent years of research in theoretical computer science in the former Soviet Union. RAIRO, Technique et science informatique, 12(1):9–28, 1993. and some remarks are in.A. Slissenko. Towards analysis of information structure of computations. The IFCoLog Journal of Logic and its Applications, 4(4):1457–1476, 2017. Published also in Volume 70 of the Studies in Logic series, pages 277-299, College Publications.

• {{MathGenealogy|id=85166}}
• [https://www.lacl.fr/slissenko/ Anatol Slissenko home page]
• [https://www.lacl.fr/slissenko/anatol_pub.html Publications of Anatol Slissenko]
• [https://www.mathnet.ru/rus/person19146 Publications of Anatol Slissenko in Russian]

{{Authority control}}

{{DEFAULTSORT:Slissenko, Anatol}}

Category:Russian mathematicians

Category:French mathematicians

Category:Living people

Category:1941 births