Primitive Program Schemes with Procedures

The paper considers algebraic program models with procedures designed to analyze program semantic properties based on program schemes. This leads to the problem of program scheme equivalence and the problem of constructing a complete system of equivalent program scheme transformations. Among algebraic program models with procedures, we focus on gateway models induced by program models without procedures and primitive program schemes belonging to these gateway models. The equivalence problem is decidable for these schemes. In the case where the inducer is a special type of program model without procedures, we construct a complete system of equivalent scheme transformations for a particular subclass of primitive program schemes.