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)