 |
|
Curriculum
vita of
Anatol Slissenko
Anatol Oles'evich Slissenko was
born on August 15, 1941. |
|
 |
|
In 1963
A. Slissenko graduated from the Faculty of Mathematics and Mechanics of
St.Petersburg (at that time Leningrad) University and joined the group
of Mathematical Logic of Leningrad Division of Steklov Mathematical Institute
of the Academy of Sciences of the USSR. The group was headed by N. Shanin
and had already among its members G. Davydov, S. Maslov, G. Mints and V.
Orevkov. |
|
|
His research at that
time was held in constructive analysis and automatic theorem-proving --
the latter was the main common activity of the group. The provers designed
and implemented by the group contained many pioneering and advanced ideas
and were very efficient in the context of that epoque. However, they were
not sufficiently powerful to find new interesting theorems. |
|
|
|
The intention to understand
the sources of such inefficiency and as well as the insufficiency of the
traditional notion of computability to understand the algorithmic problems
related to computational mathematics (that was proclaimed as one of the
goals of constructive analysis) led A. Slissenko to computational complexity.
That was in 1967. At that time the computational complexity was doing its
first steps. In the Soviet Union first fundamental results were obtained
by G. Tseitin, A. Markov, B. Trakhtenbrot and others in the late 50ies;
but there was practically no communication with the West until late 60ies. |
|
 |
|
The first major result
by A.Slissenko was designing a multi-head Turing machine which recognizes
palindromes in real time (i.e. the machine spends a constant number of
steps for each input letter). This algorithm was unexpected and was based
on a subtle theory of periods in a word developed by A.Slissenko. This
was one of the first constructions of a `fast' algorithm relied on a deep
mathematical background. One should notice that a linear time algorithm
for palindromes is obvious. |
|
 |
|
After this
result on palindromes it was natural to consider a possibility of real-time
recognizing another basic problem of pattern matching. It was known that
this problem is unsolvable by Turing machines with tapes of any dimension.
A.Slissenko has designed a real-time algorithm on a RAM (random access
machine) that solved even a much harder problem -- finding in real-time
all the periodicities in a word (in a some compact form). As a by-product
of the developed tools real-time solution for many other string-matching
problems were given (e.g. finding all longest repetitions). At the same
time A.Slissenko has introduced a concept of a machine LRAM with logarithmic
length of registers which has appeared to be an adequate modelf or the
operating memory. |
|
 |
|
In another pioneering
work he has proved that the traveling salesman problem for graphs produced
by a context-free grammar can be solved within polynomial time.
An important notion for
understanding possibilities of heuristic algorithms of proofs search was
one of the entropy of a proof system elaborated by A. Slissenko. Besides,
he has designed (with co-authors) several polynomial-time algorithms for
constructing paths avoiding obstacles, a well known problem in robotics. |
|
 |
|
In the late 60ies
A. Slissenko has organized with his colleagues a very successful and fruitful
seminar on the complexity theory in St.Petersburg and was its leader for
decades. Many its participants and the former students of A.Slissenko are
nowadays dissipated all over the world.
In 1983 A. Slissenko
was an invited speaker at the ICM in Warsaw. |
|
 |
|
In the 80s he considerably
contributed to reforming computer science education in Leningrad Polytechnic
Institute and later in Leningrad University where he was head on the department
of computer science.
|
| |
 |
|
The life conditions
under the Soviet communism were drastically degrading and with the fall
of communism became intolerable. In the fall of 1992 A. Slissenko came
to the University of Poitiers with the help of M. de Rougemont. He guards
very warm souvenirs about the ambience and people he worked with in Poitiers.
By the way there he learnt French and got his driving licence. |
|
|
|
In 1993 he got a professor
position at the UniversityParis 12 in Creteil. There he devoted his time
and his skill to create new undergraduate courses and to organize and lead
a research group that during only four years of its existence considerably
improved its position and reputation and was recommended by the Ministry
to apply for a a CNRS status. During the same time the group largely extended
its international cooperation. |
|
 |
|
The most recent domain
of research of A. Slissenko lies in program verification. With his colleagues
from the University Paris 12 he is developing a logical approach to verification
based as on traditional as well on innovative ideas like using carefully
chosen expressive logics extending decidable theories, decidable classes
based on physical properties of control systems and the corresponding verification
via complete description of counter-models, new ideas to represent heuristics
of problem-oriented automatic theorem-proving and others. |