A formalization of unique solutions of equations in process algebra

Tian, Chun (2017) A formalization of unique solutions of equations in process algebra. [Laurea magistrale], Università di Bologna, Corso di Studio in Informatica [LM-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Creative Commons: Attribuzione - Condividi allo stesso modo 3.0

Download (1MB)


In this thesis, a comprehensive formalization of Milner's Calculus of Communicating Systems (also known as CCS) has been done in HOL theorem prover (HOL4), based on an old work in HOL88. This includes all classical properties of strong/weak bisimulation equivalences and observation congruence, a theory of congruence for CCS, various versions of ``bisimulation up to'' techniques, and several deep theorems, namely the ``coarsest congruence contained in weak equivalence'', and three versions of the ``unique solution of equations'' theorem in Milner's book. This work is further extended to support recent developments in Concurrency Theory, namely the ``contraction'' relation and the related ``unique solutions of contractions'' theorem found by Prof. Davide Sangiorgi, University of Bologna. As a result, a rather complete theory of ``contraction'' (and a similar relation called ``expansion'') for CCS is also formalized in this thesis. Further more, a new variant of contraction called ``observational contraction'' was found by the author during this work, based on existing contraction relation. It's formally proved that, this new relation is preserved by direct sums of CCS processes, and has a more elegant form of the ``unique solutions of contractions'' theorem without any restriction on the CCS grammar. The contribution of this thesis project is at least threefold: First, it can be seen as a formal verification of the core results in Prof.\ Sangiorgi's paper, and it provides all details for the informal proof sketches given in the paper. Second, a large piece of old proof scripts from the time of Hol88 (1990s) has been ported to HOL4 and made available to all its users. Third, it's a proof engineering research by itself on the correct formalization of process algebra, because the work has made extensive uses of some new features (e.g. coinductive relation) provided in recent versions of HOL4 (Kananaskis-11 and later).

Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Tian, Chun
Relatore della tesi
Corso di studio
Curriculum A: Progettazione e analisi del software
Ordinamento Cds
Parole chiave
process algebra,CCS,higher order logic,HOL,contraction,unique solutions,bisimulation
Data di discussione della Tesi
20 Dicembre 2017

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento