Formal aspects of structured programming with goto statements (Q800711)

Among the well-known unstructured constructs are conditional or unconditional jumps to a given label. On the level of logical program schemata the properties of unstructured contructs are fully investigated in the framework of the theory of Yanov schemata, which constitute the foundation of traditional schematology [\textit{A. P. Ershov}, Probl. Kibern. 27, 87-110 (1973; Zbl 0315.68010)]. The structured schematalogy has been developed on the basis of the apparatus of \textit{V. M. Glushkov's} systems of algorithmic algebras (SAA) since 1965 [Kibernetika 1965, No.5, 1-9 (1965; Zbl 0156.018)]. Structured program schemata in SAA are representable by regular schemata. This paper deals with a comparative analysis of the Yanov schemata languages and regular schemata with respect to their expressive power. Let K and K' be some classes of program schemata. Let an axiomatic system \(\Sigma\) be transformationally complete with respect to the classes K and K', \(\Sigma\) [K\(\to K']\), if there is a constructive procedure based on \(\Sigma\), which transforms an arbitrary schema \(F\in K\) into an equivalent schema \(G\in K'\). An axiomatic system \(\Delta\) is developed with a single inference rule - the traditional substitution, characterizing in terms of regular schemata the essential features of the unstructured constructs represented by Yanov schemata. The axiomatics \(\Delta\) is used as a basis for a constructive procedure of Yanov schemata regularization which permits to construct an equivalent regular schema for an arbitrary Yanov schema. At the same time the inverse transformation is found to be infeasible, therefore, the property \(\Delta\) [S\(\to R]\) holds for \(\Delta\), where S (R) is a class of Yanov schemata (of regular schemata, respectively). It should be noted, that the distinctive characteristic of the obtained results in comparison with the well-known regularization algorithms is the transformation at the level of logical program schemata with no memory involved. The interchangeability of the operations of the left multiplication (process prediction), the synchronous and non- deterministic disjunctions and the right recursion in the process of Yanov schemata regularization is established which ensures ease of representation of various algorithmic processes in SAA and their formal transformation depending on the available expressive facilities and computing resources.