10.2168/LMCS-5(2:16)2009
https://lmcs.episciences.org/832
Bengtson, Jesper
Jesper
Bengtson
Parrow, Joachim
Joachim
Parrow
Formalising the pi-calculus using nominal logic
We formalise the pi-calculus using the nominal datatype package, based on
ideas from the nominal logic by Pitts et al., and demonstrate an implementation
in Isabelle/HOL. The purpose is to derive powerful induction rules for the
semantics in order to conduct machine checkable proofs, closely following the
intuitive arguments found in manual proofs. In this way we have covered many of
the standard theorems of bisimulation equivalence and congruence, both late and
early, and both strong and weak in a uniform manner. We thus provide one of the
most extensive formalisations of a process calculus ever done inside a theorem
prover.
A significant gain in our formulation is that agents are identified up to
alpha-equivalence, thereby greatly reducing the arguments about bound names.
This is a normal strategy for manual proofs about the pi-calculus, but that
kind of hand waving has previously been difficult to incorporate smoothly in an
interactive theorem prover. We show how the nominal logic formalism and its
support in Isabelle accomplishes this and thus significantly reduces the tedium
of conducting completely formal proofs. This improves on previous work using
weak higher order abstract syntax since we do not need extra assumptions to
filter out exotic terms and can keep all arguments within a familiar
first-order logic.
Comment: 36 pages, 3 figures
episciences.org
Computer Science - Logic in Computer Science
F.4.1
arXiv.org - Non-exclusive license to distribute
2015-06-25
2009-06-30
2009-06-30
eng
journal article
arXiv:0809.3960
10.48550/arXiv.0809.3960
1860-5974
10.1017/s0960129518000452
https://lmcs.episciences.org/832/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 5, Issue 2
Researchers
Students