Department of Information Technology

Abstract

We use the interactive theorem prover Isabelle to prove that the
algebraic axiomatization of bisimulation equivalence in the
pi-calculus is sound and complete. This is thefirst proof of
its kind to be wholly machine checked. Although the
result has been known for some time the proof had parts which needed
careful attention to detail to become completely formal. It is not
that the result was ever in doubt; rather, our contribution lies in
the methodology to prove completeness and get absolute certainty
that the proof is correct, while at the same time following the
intuitive lines of reasoning of the original proof. Completeness of
axiomatizations is relevant for many variants of the calculus, so
our method has applications beyond this single result. We build on
our previous effort of implementing a framework for the pi-calculus
in Isabelle using the nominal data type package, and strengthen our
claim that this framework is well suited to represent the theory of
the pi-calculus, especially in the smooth treatment of bound names.

Updated  2008-02-08 10:50:35 by Lisa Kaati.