scientific article; zbMATH DE number 3956410

From MaRDI portal
Publication:3725522





[For the entire collection see Zbl 0578.00006.] This research is an attempt to develop Backus' ideas, namely to construct a mathematical theory in which program transformations are allowed and in which correctness can be obtained using simple algebraic computations. In fact, a formal representation \(Fl_{X,T}\) of multi-input multi-exit flowchart schemes is given. (It uses a support theory T of known computation processes for redirecting flow of control and a double-ranked set X of variables for atomic schemes). A natural equivalence relation \(\equiv\) on these formal representations is considered. In the deterministic case, this equivalence \(\equiv_ d\) precisely captures having the same set of finite and infinite computation paths - that is the strong equivalence of Elgot. The algebra used for support theories in the deterministic case is a strong iteration theory (i.e. an iteration theory defined by Bloom, Elgot and Wright which obeys a functorial dagger implication). In this deterministic case the main result shows that \(Fl_{X,T}/\equiv_ d\) is the coproduct of T and the strong iteration theory freely generated by X. A partial similar result was obtained for the nondeterministic case using as support theories matrix theories endowed with an axiomatized repetition. Note: The partial result in the nondeterministic case was made much more strong by solving the open problem for a wide class of support theories, including all \(Rel_ D\). This and the results concerning the nondeterministic case will appear in Theoret. Comput. Sci., while the results concerning the deterministic case will appear in J. Comput. System Sci.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3725522)