A solution to the equivalent transformation problem in a class of primitive program schemes

The article belongs to the theory of program schemes. Program schemes are objects designed for the analysis of formalized programs. One of the key tasks of the theory is to create a finite full system of equivalent transformations (E.T.). The article deals with program schemes with procedures, limited only to gateway program models. Such models derive highly from program models without procedures. A brief description of E.T. systems is given, followed by a methodology for the construction of full systems of E.T. A subclass of gateway program models, called primitive schemes, is introduced. Such schemes are closer to procedure-free schemes. The methodology is then successfully applied to construct a full finite system of E.T. in the primitive subclass of balanced gateway semigroup program models with left cancellation, which is a well-studied class of program models. The construction is based on the known system of E.T. for similar program models without procedures. An auxiliary type of schemes, called multiexit schemes, is used. As a result, canonical schemes for classes of equivalence within the models are defined, and a sequence of transformations resulting in the transition of any scheme from this model into its canonical form is stated. This is considered a complete E.T. problem solution for a class of programs. Further research topics are given in the conclusion.