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)