Anatol Slissenko
Current
research topic:
Entropic
measures of computing (from 2011)
Topics of prior
research:
– Automatic theorem-proving (1962--1967)
– Recursive (constructive) theory of real valued
functions (1962--1967)
– Logic approach to the verification of distributed real-time
programs (1996–2006)
–
Algorithmics
and complexity:
- Recognition of
palindromes in real time by a six-head Turing machine
(1969-1973,
breakthrough result)
- Real-time
algorithm that constructs all periodicities of a word (in a compact
form) and solves (in real time) classical string-matching
problems (1978-1981,
breakthrough
result)
- Polytime algorithms
that construct shortest paths amidst semi-algebraic obstacles
(1991-2005)
- Complexity of Markov
decision processes (1994-1996)
- Graph grammars
to describe polytime classes
of hard problems (Slisenko's
grammars, 1979-1982)
- Notion of
entropie for the systemes of knowledge representation (1991)
- Notion of LRAM;
notion of computational complexity of a concrete instance of a problem
(1977-1978)
- Fault tolerance of syntax
(1990-1993)
- Algorithms for verification of hard real-time systems
(1996-2008)