A Solution to the Equivalent Transformation Problem in a Class of Primitive Program Schemes
https://doi.org/10.15514/ISPRAS-2015-27(2)-11
Abstract
The article belongs to the theory of program schemes, which are objects designed for the analysis of formalized programs. The structure of such schemes is represented as graphs. Programs schemes with procedures are considered. A subclass of program schemes, called primitive, is defined. A methodology for the construction of full systems of equivalent transformations (E.T.) is given. This methodology is then successfully applied to construct a full system of E.T. in the primitive subclass of balanced gateway program models with left cancellation. 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. Further research topics are given in the conclusion.
References
1. Podlovchenko R.I. Primitive program schemata with procedures. Automatic Control and Computer Sciences, Allerton Press, 2014, vol. 48, N 7, pp. 615-622.
2. Podlovchenko R.I., Molchanov A.E. About algebraic program models with procedures. Automatic Control and Computer Sciences, Allerton Press, 2013, vol. 47, N 7, pp. 385-392.
3. Podlovchenko R.I. Special’nie peregorodchato-avtomatnie modeli rekursivnikh programm [Special gateway-automaton models of recursive programs]. Programmirovanie [Programming], 1994, No. 3, pp. 3-26 (in Russian).
4. Molchanov A.E. Razreshimost’ ekvivalentnosti v dvuhparametricheskich peregorodchatikh modelyah programm [Equivalence Problem Solvability in Biparametric Gateway Program Models]. Modelirovanie I analiz informacionnikh sistem [Information systems analysis and modelling], 2014, vol.21, No. 4, pp. 104-115 (in Russian).
5. Podlovchenko R.I. Complete Systems of Equivalent Transformations
6. in Balanced Semigroup Models of Programs with Left Cancellation. Programming and Computer Software, 2010, vol. 36, No. 3, pp. 125-137
Review
For citations:
Molchanov A. A Solution to the Equivalent Transformation Problem in a Class of Primitive Program Schemes. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(2):173-188. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(2)-11
Email this article 