Yoshiki Kinoshita - On Completeness in Refinement

In a paper in 1986, Hoare, He and Sanders proposed a formulation of refinement for a system equivalent to the $\nu$-calculus with non- derministic choice, using a relation based semantics. To give a proof method to show that one program is a refinement of another, they introduced downward simulation and upward simulation, but the proof method based upon either of them is not complete with respect to their notion of refinement, so they claimed ``joint'' completeness based upon both notions of simulation with respect to their notion of refinement.

We give a new definition of refinement in terms of structure respecting lax transformations, and show that the proof method based upon downward simulation is complete with respect to this notion of refinement. We present our theory for the $\nu$-calculus and the $\mu$-calculus, both with nondeterministic choice. We use results in enriched category theory to show this, and the central notion here is that of algebraic structure on locally ordered categories, not on sets. Our definition of refinement is neither a restriction nor a generalisation of Hoare, He and Sanders' definition, but we include all their important examples.

This talk contains materials in joint work with John Power and joint work with Hiroshi Watanabe.