Publications
No fulltext in DiVA
Author:
Bengtson, Jesper (Uppsala University, Department of Information Technology)(datorteknik)(Uppsala University, Computer Systems) (datorteknik)
Parrow, Joachim (Uppsala University, Department of Information Technology)(datorteknik)(Uppsala University, Computer Systems) (datorteknik)
Title:
A completeness proof for bisimulation in the pi-calculus using Isabelle
Department:
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology
Publication type:
Article in journal (Refereed)
Language:
English
In:
Electronic Notes in Theoretical Computer Science
Volume:
192
Issue:
1
Pages:
61-75
Year of publ.:
2007
URI:
urn:nbn:se:uu:diva-12084
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-12084
Subject category:
Computer science
Computer science
Keywords(en) :
pi-calculus, Theorem Provers, Isabelle, Bisimulation, Axiomatization
Abstract(en) :

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 the first 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.

Available from:
2007-11-23
Statistics:
37 hits