An Algebraic Definition of Simulation Between Programs

Milner, Robin

An Algebraic Definition of Simulation Between Programs

Download BibTeX Cite

Proceedings of the Second International Joint Conference on Artificial Intelligence. Pages 481-488.

Abstract

A simulation relation between programs is defined which is a 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 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 Floyd's technique for proving correctness of programs. Finally, necessary and sufficient conditions for simulation are given.

Robin Milner. 1971. An Algebraic Definition of Simulation Between Programs. In Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI-71. IJCAI, 481–488. https://ijcai.org/proceedings/1971/50

@inproceedings{ijcai1971p50,
  title     = {An Algebraic Definition of Simulation Between Programs},
  author    = {Milner, Robin},
  booktitle = {Proceedings of the Second International Joint Conference on
               Artificial Intelligence, {IJCAI-71}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {D.C. Cooper},
  pages     = {481--488},
  year      = {1971},
  url       = {https://ijcai.org/proceedings/1971/50},
}

TY  - CPAPER
TI  - An Algebraic Definition of Simulation Between Programs
AU  - Milner, Robin
T2  - Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI-71
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1971
SP  - 481
EP  - 488
UR  - https://ijcai.org/proceedings/1971/50
ER  -