Ivannikov Institute for System Programming of the RAS

The equivalence problem for computational models: decidable and undecidable cases.


Zakharov V.A.


Equivalence checking problem, program schemata, decidability This paper presents a survey of fundamental concepts and main results in studying the equivalence problem for computer programs. We introduce some of the most-used models of computer programs, give a brief overview of the attempts to refine the boarder between decidable and undecidable cases of the equivalence problem for these models, and discuss the techniques for proving the decidability of the equivalence problem.

Text of article


program, program scheme, equivalence checking, decidability, complexity


Proceedings of the Third International Conference, MCU 2001 Chişinau, Moldova, May 23–27, 2001, Lecture Notes in Computer Science, v. 2055, pp. 133-153.

Research Group

Theoretical Computer Science

All publications during 2001 All publications