An Algebraic Definition of Simulation Between Programs.

Robin Milner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.
Original languageEnglish
Title of host publicationIJCAI
Subtitle of host publicationProceedings of the 2nd International Joint Conference on Artificial Intelligence. London, UK, September 1971
EditorsD. C. Cooper
PublisherWilliam Kaufmann Inc.
Pages481-489
Number of pages9
Publication statusPublished - 1971

Keywords

  • dblp

Fingerprint

Dive into the research topics of 'An Algebraic Definition of Simulation Between Programs.'. Together they form a unique fingerprint.

Cite this