Accession Number:

AD0731383

Title:

An Algebraic Definition of Simulation Between Programs,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1971-02-01

Pagination or Media Count:

24.0

Abstract:

A simulation relation between programs is defined which is quasi-ordering. Mutual simulation is then an equivalence relation, and by dividing out by it one abstracts from a program such details as how the sequencing is controlled and how data is presented. The equivalence classes are approximations 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 Floyds technique for proving correctness of programs. Finally, necessary and sufficient conditions for simulation are given. Author

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE