Defense Technical Information Center (DTIC) · 1971 · 533 citations · 2 references
ComputingComputer ScienceAlgorithmsProgramming LanguagesTheory Of ComputationEquivalence CheckingSimulation MethodsSimulation ModelingComputational EquivalenceEquivalence ClassesProgram EquivalenceSimulation EquivalenceSimulation RelationsSimulation Semantics
Equivalence classes of programs approximate the algorithms implemented by their member programs. The paper defines a quasi‑ordering simulation relation between programs. The authors present a technique, analogous to Floyd’s method, for proving simulation and equivalence of programs. Mutual simulation is shown to be an equivalence relation that abstracts away sequencing and data representation details, and necessary and sufficient conditions for simulation are provided.
A simulation relation between programs is defined which is quasi-ordering. Mutual simulation is then an equivalence relation, and by dividing out by it we abstract from a program such details as how the sequencing is controlled and how data is represented. The equivalence classes are approxiamtions to the algorithms which are realized, or expressed, by their member programs. A technique is given and illustrated for proving simulation and equivalence of programs; there is an analogy with Floyd''s technique for proving correctness of programs. Finally, necessary and sufficient conditions for simulation are given.
2
Zohar Manna · Journal of Computer and System Sciences · 1969 · 132 citations
FORMALIZATION OF PROPERTIES OF PARALLEL PROGRAMS
E. A. Ashcroft, Zohar Manna · 1970 · 68 citations