No label defined (Q3725522)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3956410
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3956410 |
Statements
1986
0 references
algebraic semantics
0 references
feedback
0 references
program transformations
0 references
correctness
0 references
flowchart schemes
0 references
iteration
0 references
repetition
0 references
0.9231535
0 references
0.9115138
0 references
0 references
[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.
0 references