We present a refinement ordering between binary relations, viewed as programs or specifications. This ordering induces a complete join semilattice that can be embedded in a relation algebra. This embedding then allows an easy proof of many properties of the refinement semilattice, by making use of the well-known corresponding properties of relation algebras. The operations of the refinement semilattice corresponding to join and composition in the embedding algebra are, respectively, demonic join and demonic composition. The weakest prespecification and postspecification operators of Hoare and He, defined over a relation algebra, also have corresponding operators in the semilattice.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)