Unique solutions of contractions, CCS, and their HOL formalisation - Archive ouverte HAL Access content directly
Journal Articles Information and Computation Year : 2020

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.
Fichier principal
Vignette du fichier
main.pdf (789.26 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03120563 , version 1 (25-01-2021)

Identifiers

Cite

Chun Tian, Davide Sangiorgi. Unique solutions of contractions, CCS, and their HOL formalisation. Information and Computation, 2020, 275, pp.104606. ⟨10.1016/j.ic.2020.104606⟩. ⟨hal-03120563⟩
58 View
186 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More