Anatol Olesjewitsch Slissenko
Anatol Olesjewitsch Slissenko (russisch Анатоль Олесьевич Слисенко, englische Transkription Anatol Olesevich Slissenko, auch Slisenko; * 15. August 1941) ist ein russischer Mathematiker und Informatiker, der sich mit Komplexitätstheorie, Computeralgebra und anderen Bereichen der theoretischen Informatik befasst.
Slissenko studierte an der Staatlichen Universität Leningrad mit dem Diplom 1963 und wurde 1967 bei Nikolai Alexandrowitsch Schanin am Steklow-Institut in Leningrad promoviert (Dissertation: Regulatoren der Konvergenz von konstruktiven Folgen und Regulatoren der Stetigkeit von konstruktiven Funktionen (Russisch))[1] und 1981 habilitiert (russischer Doktortitel). 1967 bis 1992 stand er dem Leningrader Seminar für Komplexitätstheorie vor und 1981 bis 1993 leitete er das Labor für Algorithmentheorie des Leningrader Instituts für Informatik und Automation der Russischen Akademie der Wissenschaften. Außerdem war er 1981 bis 1987 in Teilzeit Professor am Polytechnischen Institut in Leningrad und 1988 bis 1992 an der Staatlichen Universität Leningrad, wo er die Fakultät für Informatik leitete.
1993 bis 2009 war er Professor an der Universität Paris XII. Seit 2009 ist er dort Professor Emeritus. Dort leitete er 1997 bis 2007 das Labor für algorithmische Komplexität und Logik (LACL).
Er befasst sich neben Komplexitätstheorie (u. a. Anfang der 1970er Jahre eine Turingmaschine mit sechs Lese/Schreibköpfen, die Palindrome in Echtzeit erkennt) und Algorithmen (u. a. Ende der 1970er Jahre Echtzeit-Algorithmen, die alle Periodizitäten eines Wortes in kompakter Form finden und klassische String-Matching-Probleme lösen) auch mit automatischen Beweissystemen (1960er Jahre), rekursiver (konstruktiver) Theorie reeller Funktionen, Graph-Grammatiken (eine bestimmte Art davon ist nach ihm benannt, für die Beschreibung von Polyzeit-Klassen schwieriger Probleme), probabilistischen Methoden in der theoretischen Informatik (Entropie-artige Konzepte für die Algorithmenanalyse und Wissensdarstellung), Komplexität von Markow-Entscheidungsprozessen, Fehlertoleranz von Syntax und Verifizierung von Echtzeitsystemen und verteilten Systemen.
1983 war er eingeladener Sprecher auf dem Internationalen Mathematikerkongress in Warschau (Linguistic considerations in deriving effective algorithms).
Zu seinen Doktoranden zählt Dmitri Jurjewitsch Grigorjew.
Schriften (Auswahl)
- Complexity problems in computational theory, Russian Mathematical Surveys, Band 36, 1981, S. 23–125
- Recognizing a symmetry predicate by multihead Turing machines with input. Proc. Steklov Inst. of Mathematics, AMS, Band 129, 1976, S. 25–208
- Detection of periodicities and string-matching in real time. J. of Soviet Mathematics, Band 22, 1983, S. 1316–1386
- Context-free grammars as a tool for describing polynomial-time subclasses of hard problems. Inform. Process. Lett., Band 14, 1982, S. 52–56
- mit Danièle Beauquier: A first order logic for specification of timed algorithms: basic properties and a decidable class. Annals of Pure and Applied Logic, Band 113, 2002, S. 13–52
- mit J. Heintz, T. Krick, P. Solerno: Finding shortest paths around semi-algebraic obstacles in the plane, J. of Math. Sci., Band 70, 1994, S. 1944–1949
- mit D. Grigoriev: Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane, St. Petersburg Math. J., Band 10, 1999, S. 315–332
- On measures of information quality of knowledge processing systems. Information Sciences: An International Journal, Band 57/58, 1991, S. 389–402
- On entropic convergence of algorithms in terms of domain partitions, Arxiv 2016