Studies in the theory of algebraic models of programs with procedures

Abstract

Algebraic models of programs with procedures extend algebraic models of programs that are free of procedures (simple models of programs). A specific feature of both types of models is that they are built for some formalization of software programs. Models of programs are intended for studying functional equivalence of formalized programs and constructing wide sets of equivalent transformations of programs. Two basic problems in the theory of algebraic models of programs are the equivalence problem and the problem of building complete systems of equivalent transformations. An increasing interest in models of programs with procedures is due to the abundance of results obtained for simple models of programs. The most suitable model of programs with procedures is a gateway model. A remarkable feature of these models is that every such model is induced by some simple model of programs. This paper gives a survey of the latest results obtained for gateway models of programs.