Weak equivalence in a class of structured program schemes

DOI10.1016/0022-0000(84)90016-3MaRDI QIDQ797988zbMATH OpenOpenAlexFDO

Authors Douglas R. Troeger

Publication date 1984

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(84)90016-3

zbMATH Keywords

flowchartsstructured programmingweak equivalence

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

Given predicates \(P_ i\) and biscalar \(F_ i\), \(l\leq i\leq n\), the operation \(\Omega_ n(P_ 1,F_ 1,...,P_ n,F_ n)\) yields a scheme. For any positive integer \(n,BJ_ n\) is defined to be the least class of schemes containing the trivial scheme and the atomic schemes closed under composition, binary alternation, and the operations \(\Omega_ i\), 1\(\leq i\leq n\). \(BJ_ 1\) is the well-known class of D-schemes. Two program schemes are weakly equivalent if they compute the same partial function in every interpretation: equational axioms for the weak equivalence of strongly free \(BJ_ n\) schemes are presented. It follows from the proof of the completeness of these axioms that there is a unique minimal strongly free \(BJ_ n\) scheme weakly equivalent to a given strongly free \(BJ_ n\) scheme. This result is used to design an algorithm which optimizes strongly free D-schemes: given a strongly free D-scheme F, it is possible to construct the unique minimal strongly free D-scheme \(F_ M\) weakly equivalent to F in time proportional to the square of the number of nonexit vertices of F.

Recommendations

• scientific article; zbMATH DE number 3928354
• Decidability of strong equivalence for subschemas of a class of linear, free, near-liberal program schemas
• An algebraic approach to schemes of structured programs
• An algorithm deciding functional equivalence in a new class of program schemes
• Axiomatizing schemes and their behaviors

Cites work

• A Perspective View of Discrete Automata and Their Design
• Algebraic and graph theoretic characterizations of structured flowchart schemes
• An axiomatization of D-scheme strong equivalence
• Analysis of structured programs
• scientific article; zbMATH DE number 33213 (Why is no real title available?)
• On the Computational Complexity of Program Scheme Equivalence

Cited in

(4)

• scientific article; zbMATH DE number 3928354 (Why is no real title available?)
• scientific article; zbMATH DE number 850400 (Why is no real title available?)
• Decidability of strong equivalence for subschemas of a class of linear, free, near-liberal program schemas
• An algorithm deciding functional equivalence in a new class of program schemes

This page was built for publication: Weak equivalence in a class of structured program schemes

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