Unique solutions of contractions, CCS, and their HOL formalisation

Abstract

The unique solution of contractions is a proof technique for (weak) bisimilarity that overcomes certain syntactic limitations of Milner's “unique solution of equations” theorem. This paper presents an overview of a comprehensive formalisation of Milner's Calculus of Communicating Systems (CCS) in the HOL theorem prover (HOL4), with a focus towards the theory of unique solutions of equations and contractions. The formalisation consists of about 24,000 lines (1MB) of code in total. Some refinements of the “unique solution of contractions” theory itself are obtained. In particular we remove the constraints on summation, which must be guarded, by moving from contraction to rooted contraction. We prove the “unique solution of rooted contractions” theorem and show that rooted contraction is the coarsest precongruence contained in the contraction preorder. Show more