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

Authors

Zakharov V.A.

Abstract

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

Keywords

program, program scheme, equivalence checking, decidability, complexity

Edition

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